__故人__：目前看来是DIJ太慢了？？？ int fa[max_n],v[max_n]; queue<int> q; void spfa(int s){ memset(dist,0x3f,sizeof(dist)); q.push(s);v[s]=1;dist[s]=0; while(!q.empty()){ int x=q.front();v[x]=0;q.pop(); for(int i=head[x];i;i=E[i].next){ int y=E[i].to,z=E[i].cost; if(dist[y]>dist[x]+z){ dist[y]=dist[x]+z; fa[y]=x; if(!v[y]) q.push(y),v[y]=1; } else if(dist[y]==dist[x]+z)fa[y]=min(fa[y],x); } } } 换成SPFA就过了，迷惑？