正反两边spfa，最后取个max就可以了。
#include<cstdio> #include<cstring> #include<cmath> #include<algorithm> #define fo(i,a,b) for(int i=a;i<=b;i++) #define fd(i,a,b) for(int i=a;i>=b;i--) using namespace std; const int N=2e5,M=2e3+5; int head[N],next[N],go[N],v[N],tot=0; int dis[M],vis[M],h[M],n,m,k,fa[N]; int ans[N]; typedef long long ll; inline void add(int x,int y,int z) { go[++tot]=y; v[tot]=z; next[tot]=head[x]; head[x]=tot; } inline void spfa(int s) { memset(dis,127,sizeof(dis)); int t=0,w=1; dis[s]=0; h[t]=s;vis[s]=1; while (t!=w) { int x=h[t++]; int i=head[x]; while (i) { int to=go[i]; if (dis[to]>dis[x]+v[i]) { dis[to]=dis[x]+v[i]; if (!vis[to]) { vis[to]=1; h[w++]=to; } } i=next[i]; } vis[x]=0; } } int main() { scanf("%d%d%d",&n,&m,&k); fo(i,1,m) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); } fo(i,1,n) { spfa(i),ans[i]=dis[k]; } spfa(k); int mx=0; fo(i,1,n)mx=max(mx,dis[i]+ans[i]); printf("%d\n",mx); return 0; } 