首页 > 代码库 > 图论 ---- spfa + 链式向前星 ---- poj 3268 : Silver Cow Party
图论 ---- spfa + 链式向前星 ---- poj 3268 : Silver Cow Party
| Time Limit: 2000MS | Memory Limit: 65536K | |
| Total Submissions: 12674 | Accepted: 5651 |
Description
One cow from each of N farms (1 ≤ N ≤ 1000) conveniently numbered 1..N is going to attend the big cow party to be held at farm #X (1 ≤ X ≤ N). A total of M (1 ≤ M ≤ 100,000) unidirectional (one-way roads connects pairs of farms; road i requires Ti (1 ≤ Ti ≤ 100) units of time to traverse.
Each cow must walk to the party and, when the party is over, return to her farm. Each cow is lazy and thus picks an optimal route with the shortest time. A cow‘s return route might be different from her original route to the party since roads are one-way.
Of all the cows, what is the longest amount of time a cow must spend walking to the party and back?
Input
Lines 2..M+1: Line i+1 describes road i with three space-separated integers: Ai, Bi, and Ti. The described road runs from farm Ai to farm Bi, requiring Ti time units to traverse.
Output
Sample Input
4 8 21 2 41 3 21 4 72 1 12 3 53 1 23 4 44 2 3
Sample Output
10
Hint
Source
Mean:
原意：草场上有n个农场，农场之间有一些路径，每个农场里住着一头牛，现在x农场的牛要过生日开party，其他农场的牛要到该农场去参加party，现在让你选择一头来回耗时最多的一头牛出来，输出时间。
给你一个n个结点、m条边的有向图，现在要你求从n-1个结点到达指定的一个结点的来回最长路。
analyse:
这题思路很巧妙，我们在存图的时候用链式向前星来存，存的时候就建两次边，一次正向，一次反向，用一个flag来标记一下。然后用两遍spfa，第一遍求出从x点出发的正向图到每个结点的最短路，第二遍求出从x点出发的反向图到每个结点的最短路，最后将两次的最短路对应相加，求出最大值即为最终的answer。
Time complexity：O(n*k)
Source code：
//Memory Time// 3521K 241MS//by : Snarl_jsb#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<iomanip>#include<string>#include<climits>#include<cmath>#define MAXV 1010#define MAXE 100010#define LL long longusing namespace std;namespace Adj{ struct Node { int to,next,val; bool flag; } edge[MAXE<<1]; int top,head[MAXV]; void init() { top=1; memset(head,0,sizeof(head)); } void addEdge(int u,int v,int val) { edge[top].to=v; edge[top].val=val; edge[top].flag=1; edge[top].next=head[u]; head[u]=top++; edge[top].to=u; edge[top].val=val; edge[top].flag=0; edge[top].next=head[v]; head[v]=top++; }}using namespace Adj;int n,m,x,ans;bool vis[MAXV];int dis[MAXV];int dis1[MAXV];void spfa(bool flag){ memset(vis,0,sizeof(vis)); for(int i=0;i<=n;i++) dis[i]=INT_MAX; queue<int>Q; Q.push(x); vis[x]=1; dis[x]=0; while(!Q.empty()) { int now=Q.front(); Q.pop(); vis[now]=0; for(int i=head[now];i;i=edge[i].next) { if(flag==1) { if(edge[i].flag==0) continue; } else { if(edge[i].flag==1) continue; } int son=edge[i].to; int val=edge[i].val; if(dis[now]+val<dis[son]) { dis[son]=dis[now]+val; if(!vis[son]) { vis[son]=1; Q.push(son); } } } } if(flag==1) { for(int i=1;i<=n;i++) dis1[i]=dis[i]; } else { int Max=INT_MIN; for(int i=1;i<=n;i++) { dis[i]+=dis1[i]; if(dis[i]>Max) Max=dis[i]; } ans=Max; }}int main(){// freopen("cin.txt","r",stdin);// freopen("cout.txt","w",stdout); while(~scanf("%d %d %d",&n,&m,&x)) { init(); int u,v,w; while(m--) { scanf("%d %d %d",&u,&v,&w); addEdge(u,v,w); } spfa(1); spfa(0); printf("%d\n",ans); } return 0;}