QAQ 有两个操作，一个是单源最短路的起点，一个是单源最短路的终点，前一个好说，直接以x为起点跑SPFA就行了，至于后一个，我们只需要把路反过来建，然后在跑一边SPFA就行了233
#include <cstdio> #include <iostream> #include <algorithm> #include <queue> #include <cstring> using namespace std; int head[9999],to[200000],cost[200000],net[200000]; int dis[9999],f[9999]; int dis2[9999]; int d[9999]; int cnt; int head2[9999],to2[200000],cost2[200000],net2[200000]; int cnt2; void add(int x,int y,int z) { cnt++; to[cnt]=y; cost[cnt]=z; net[cnt]=head[x]; head[x]=cnt; } void add2(int x,int y,int z) { cnt2++; to2[cnt2]=y; cost2[cnt2]=z; net2[cnt2]=head2[x]; head2[x]=cnt2; } int n,m,s; int maxf1; void spfa1(int s) { memset(dis,127,sizeof(dis)); dis[s]=0; d[1]=s; f[s]=1; int h=0,tail=1; do { h++; int dd=d[h]; f[dd]=0; for(int i=head[dd];i;i=net[i]) { int p=to[i]; if(dis[p]>dis[dd]+cost[i]) { dis[p]=dis[dd]+cost[i]; if(!f[p]) { d[++tail]=p; f[p]=1; } } } }while(h<tail); } void spfa2(int s) { memset(dis2,127,sizeof(dis)); memset(f,0,sizeof(f)); dis2[s]=0; d[1]=s; f[s]=1; int h=0,tail=1; do { h++; int dd=d[h]; f[dd]=0; for(int i=head2[dd];i;i=net2[i]) { int p=to2[i]; if(dis2[p]>dis2[dd]+cost2[i]) { dis2[p]=dis2[dd]+cost[i]; if(!f[p]) { d[++tail]=p; f[p]=1; } } } }while(h<tail); } int main() { scanf("%d%d%d",&n,&m,&s); for(int i=1;i<=m;i++) { int x,y,z; scanf("%d%d%d",&x,&y,&z); add(x,y,z); add2(y,x,z); } spfa1(s); spfa2(s); for(int i=1;i<=n;i++) maxf1=max(dis[i]+dis2[i],maxf1); printf("%d",maxf1); return 0; }