第一次接触这种分层spfa
类似于dp 个人理解
#include#include #include #include using namespace std;struct node{ int p; int v; int l; int x;};struct que{ int p; int v;};queue 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);}