第一次接触这种分层spfa
类似于dp 个人理解
#include<cstdio>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
struct node
{
int p;
int v;
int l;
int x;
};
struct que
{
int p;
int v;
};
queue<que>q;
node l[100000];
int h[501],t;
int pp[500][510],pv[500][510];
bool vis[500][510];
double map[500][510];
void add(int a,int b,int c,int d)
{
l[++t].p=b;
l[t].v=c;
l[t].l=d;
l[t].x=h[a];
h[a]=t;
}
void print(int a,int b)
{
if(a!=1)
print(pp[a][b],pv[a][b]);
printf("%d ",a-1);
}
int main()
{
int n,m,end;
scanf("%d%d%d",&n,&m,&end);
end+=1;
int a,b,c,d;
for(int i=1;i<=m;i++)
{
scanf("%d%d%d%d",&a,&b,&c,&d);
a+=1;
b+=1;
add(a,b,c,d);
}
for(int i=1;i<=n;i++)
for(int j=1;j<=510;j++)
map[i][j]=0x7ffffff;
vis[1][70]=true;
map[1][70]=0;
que pa,net;
pa.p=1;
pa.v=70;
q.push(pa);
while(!q.empty())
{
pa=q.front();
q.pop();
vis[pa.p][pa.v]=false;
for(int i=h[pa.p];i;i=l[i].x)
{
if(l[i].v==0)
{
if(map[l[i].p][pa.v]>1.0*map[pa.p][pa.v]+1.0*l[i].l/pa.v)
{
map[l[i].p][pa.v]=1.0*map[pa.p][pa.v]+1.0*l[i].l/pa.v;
pp[l[i].p][pa.v]=pa.p;
pv[l[i].p][pa.v]=pa.v;
if(!vis[l[i].p][pa.v])
{
vis[l[i].p][pa.v]=true;
net.p=l[i].p;
net.v=pa.v;
q.push(net);
}
}
}
else
{
if(map[l[i].p][l[i].v]>1.0*map[pa.p][pa.v]+1.0*l[i].l/l[i].v)
{
map[l[i].p][l[i].v]=1.0*map[pa.p][pa.v]+1.0*l[i].l/l[i].v;
pp[l[i].p][l[i].v]=pa.p;
pv[l[i].p][l[i].v]=pa.v;
if(!vis[l[i].p][l[i].v])
{
vis[l[i].p][l[i].v]=true;
net.p=l[i].p;
net.v=l[i].v;
q.push(net);
}
}
}
}
}
double minn=0x7ffffff;
for(int i=1;i<=500;i++)
if(minn>map[end][i])
{
minn=map[end][i];
a=pp[end][i];
b=pv[end][i];
}
print(a,b);
printf("%d",end-1);
}