https://www.luogu.org/problem/show?pid=1821
大体描述一下题意：一张图，边为有向边，给出一个点 s，求其它点最大的从 x 到 s 和从 s 到 x 的最短路之和。
机智的做法：我们可以跑两遍spfa，先跑出 s 到其它点的最短路，在将所有边反过来，再对 s 跑一边spfa， 那么第二遍求的就是其它点到 s 的最短路径。 是不是很机智呢 QAQ
#include<iostream> #include<cstdio> #include<queue> #include<cstring> using namespace std; int n,m,s; int head[1009],nxt[100009],num[100009],d[100009],cnt; int head2[1009],nxt2[100009],num2[100009],d2[100009],cnt2; int dis[1009],dis2[1009]; bool f[1009],f2[1009]; void add(int x,int y,int z) { cnt++;cnt2++; num[cnt]=y;num2[cnt2]=x; nxt[cnt]=head[x];nxt2[cnt2]=head2[y]; head[x]=cnt;head2[y]=cnt; d[cnt]=z;d2[cnt2]=z; } void spfa() { queue <int> q; memset(dis,127,sizeof(dis)); dis[s]=0; q.push(s); while(!q.empty()) { int k=q.front();q.pop(); f[k]=0; for(int i=head[k];i;i=nxt[i]) { int x=num[i]; if(dis[x]>dis[k]+d[i]) { dis[x]=dis[k]+d[i]; if(!f[x]) { f[x]=1; q.push(x); } } } } } void spfa2() { queue <int> q; memset(dis2,127,sizeof(dis2)); dis2[s]=0; q.push(s); while(!q.empty()) { int k=q.front();q.pop(); f2[k]=0; for(int i=head2[k];i;i=nxt2[i]) { int x=num2[i]; if(dis2[x]>dis2[k]+d2[i]) { dis2[x]=dis2[k]+d2[i]; if(!f2[x]) { f2[x]=1; q.push(x); } } } } } 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); } spfa(); spfa2(); int maxn=0; for(int i=1;i<=n;i++) { maxn=max(maxn,dis[i]+dis2[i]); } printf("%d",maxn); return 0; }