其实还是从一个x点出发到所有点的最短路问题。来和回只需分别处理一下逆图和原图，两次SPFA就行了。
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<string> #include<cmath> #include<map> #include<set> #include<vector> #include<algorithm> #include<stack> #include<queue> #include<cctype> #include<sstream> using namespace std; #define pii pair<int,int> #define LL long long int const int eps=1e-8; const int INF=1000000000; const int maxn=1000+10; int n,m,x,a,b,t; vector<int>vv1[maxn]; vector<int>vv2[maxn]; int t1[maxn][maxn],t2[maxn][maxn]; int d1[maxn],d2[maxn],ans=0; //以上1是原图的量，2是逆图的量 queue<int>q; void spfa(int type) { if(type==1) { q.push(x); while(!q.empty()) { int tt=q.front(); q.pop(); int st=vv1[tt].size(); for(int i=0;i<st;i++) { int ti=vv1[tt][i]; if(d1[tt]+t1[tt][ti]<d1[ti]) { d1[ti]=d1[tt]+t1[tt][ti]; q.push(ti); } } } } else { q.push(x); while(!q.empty()) { int tt=q.front(); q.pop(); int st=vv2[tt].size(); for(int i=0;i<st;i++) { int ti=vv2[tt][i]; if(d2[tt]+t2[tt][ti]<d2[ti]) { d2[ti]=d2[tt]+t2[tt][ti]; q.push(ti); } } } } } int main() { //freopen("in8.txt","r",stdin); //freopen("out.txt","w",stdout); scanf("%d%d%d",&n,&m,&x); fill(d1,d1+maxn,INF); fill(d2,d2+maxn,INF); d1[x]=d2[x]=0; for(int i=0;i<m;i++) { scanf("%d%d%d",&a,&b,&t); t1[a][b]=t2[b][a]=t; vv1[a].push_back(b); vv2[b].push_back(a); } spfa(1); spfa(2); for(int i=1;i<=n;i++) { ans=max(ans,d1[i]+d2[i]); } printf("%d ",ans); //fclose(stdin); //fclose(stdout); return 0; }