题目大意:n个点,m条边的有向图,给定一个点x,现在要求所有点出发到x再回到各自的点的总路程的最大值。
题目分析:有向图,求来回距离和的最大值。我们可以将这段路程分成2部分:先走到x,再从x到各点。从x回到各点好办,就是一个单源最短路的问题。但是要求从各点到x的距离,可以反过来求,因为是有向图,所以建一个反图,这样从所有点到x就又变成了从x到所有点,又变成了一个单源最短路。所以本题只要在原图和反图上都以x为源点跑一次最短路,最后在统计一下求出最大值即可。
详情请见代码:
#include <iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N = 1005; const int M = 100005; const int INF = 0x3f3f3f3f; struct node { int to,next,val; }g[M],gt[M]; int queue[M]; int front,rear; int num; int headg[N],headgt[N]; bool flag[N]; int dis1[N],dis2[N]; int st,n,m; void buildg(int s,int e,int v) { g[num].to = e; g[num].val = v; g[num].next = headg[s]; headg[s] = num; } void buildgt(int s,int e,int v) { gt[num].to = e; gt[num].val = v; gt[num].next = headgt[s]; headgt[s] = num ++; } void SPFA1() { int i,u; for(i = 1;i <= n;i ++) { dis1[i] = INF; flag[i] = false; } dis1[st] = 0; flag[st] = true; front = rear = 0; queue[rear ++] = st; while(front < rear) { u = queue[front ++]; flag[u] = false; for(i = headg[u];i != -1;i = g[i].next) { if(dis1[g[i].to] > dis1[u] + g[i].val) { dis1[g[i].to] = dis1[u] + g[i].val; if(flag[g[i].to] == false) { flag[g[i].to] = true; queue[rear ++] = g[i].to; } } } } } void SPFA2() { int i,u; for(i = 1;i <= n;i ++) { dis2[i] = INF; flag[i] = false; } dis2[st] = 0; flag[st] = true; front = rear = 0; queue[rear ++] = st; while(front < rear) { u = queue[front ++]; flag[u] = false; for(i = headgt[u];i != -1;i = gt[i].next) { if(dis2[gt[i].to] > dis2[u] + gt[i].val) { dis2[gt[i].to] = dis2[u] + gt[i].val; if(flag[gt[i].to] == false) { flag[gt[i].to] = true; queue[rear ++] = gt[i].to; } } } } } int main() { int i,a,b,c; while(~scanf("%d",&n)) { scanf("%d%d",&m,&st); num = 0; memset(headg,-1,sizeof(headg)); memset(headgt,-1,sizeof(headgt)); for(i = 1;i <= m;i ++) { scanf("%d%d%d",&a,&b,&c); buildg(a,b,c); buildgt(b,a,c); } SPFA1(); SPFA2(); int ans = -1; for(i = 1;i <= n;i ++) if(ans < dis1[i] + dis2[i]) ans = dis1[i] + dis2[i]; printf("%d\n",ans); } return 0; } //316K 16MS