http://poj.org/problem?id=3268
题意：N块田中(1≤N≤1000)都有1只牛去参加盛大的母牛聚会，这个聚会被安排在X号田(1≤X ≤N)。一共有M( 1≤M≤100,000)条单行道分别连接着两块田，且通过路i需要花Ti(1≤Ti≤100)的时间。每头母牛必需参加宴会并且在宴会结束时回到自己的田地，但是每头牛都很懒而喜欢选择化是最少的一个方案。来时的路和去时的可能不一样。求每头牛要来回的最短时间。
http://www.hankcs.com/program/cpp/poj-3268-silver-cow-party.html
dijkstra是解决单源最短路问题的，稍微修改一下就可以支持任意两点最短路：
用warshall_floyd的话会TLE，10003复杂度果然不是盖的.
http://www.cnblogs.com/Jason-Damon/archive/2012/04/29/2476285.html
2.SPFA
Read full article from 3268 -- Silver Cow Party
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?
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
Line 1: Three space-separated integers, respectively: N, M, and X
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.
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
Line 1: One integer: the maximum of time any one cow must walk.
Sample Input
4 8 2 1 2 4 1 3 2 1 4 7 2 1 1 2 3 5 3 1 2 3 4 4 4 2 3
Sample Output
10
题意：N块田中(1≤N≤1000)都有1只牛去参加盛大的母牛聚会，这个聚会被安排在X号田(1≤X ≤N)。一共有M( 1≤M≤100,000)条单行道分别连接着两块田，且通过路i需要花Ti(1≤Ti≤100)的时间。每头母牛必需参加宴会并且在宴会结束时回到自己的田地，但是每头牛都很懒而喜欢选择化是最少的一个方案。来时的路和去时的可能不一样。求每头牛要来回的最短时间。
http://www.hankcs.com/program/cpp/poj-3268-silver-cow-party.html
dijkstra是解决单源最短路问题的，稍微修改一下就可以支持任意两点最短路：
// 从顶点from指向顶点to的权值为cost的边struct edge{ int to, cost; edge(){} edge(int to, int cost) : to(to), cost(cost){}};// first 最短路径，second顶点编号typedef pair<int, int> P;// 图vector<edge> G[MAX_V];// 最短距离int d[MAX_V][MAX_V];// V是顶点数，E是边数int V, E;
// 求解从顶点s出发到所有点的最短距离
void dijkstra(int s){ priority_queue<P, vector<P>, greater<P> > que; memset(d[s], 0x3f, MAX_V * sizeof(int)); d[s][s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (d[s][v] < p.first) continue; for (int i = 0; i < G[v].size(); ++i) { edge e = G[v][i]; if (d[s][e.to] > d[s][v] + e.cost) { d[s][e.to] = d[s][v] + e.cost; que.push(P(d[s][e.to], e.to)); } } }}int main(int argc, char *argv[]){ int M, X; cin >> V >> M >> X; --X; while (M--) { int A, B, T; cin >> A >> B >> T; --A; --B; G[A].push_back(edge(B, T)); } for (int i = 0; i < V; ++i) { dijkstra(i); } int ans = 0; for (int i = 0; i < V; ++i) { if (i == X) { continue; } ans = max(ans, d[i][X] + d[X][i]); } return 0;}
不过上面那个实在太浪费，我只想计算起点或终点是X的路径最短路问题，可以在上面while (!que.empty())的循环里加入判断条件，还可以这么玩：
来一个反向图，交换边的起点和终点得到反向的有向图，两次dijkstra解决问题：
// first 最短路径，second顶点编号typedef pair<int, int> P;// 图vector<vector<edge> > G(MAX_V);// 反向图vector<vector<edge> > RG(MAX_V);// 最短距离int d[MAX_V];int rd[MAX_V];// V是顶点数，E是边数int V, E;// 求解从顶点s出发到所有点的最短距离void dijkstra(int s){ priority_queue<P, vector<P>, greater<P> > que; memset(d, 0x3f, sizeof(d)); d[s] = 0; que.push(P(0, s)); while (!que.empty()) { P p = que.top(); que.pop(); int v = p.second; if (d[v] < p.first) continue; for (int i = 0; i < G[v].size(); ++i) { edge e = G[v][i]; if (d[e.to] > d[v] + e.cost) { d[e.to] = d[v] + e.cost; que.push(P(d[e.to], e.to)); } } }}int main(int argc, char *argv[]){ int M, X; cin >> V >> M >> X; --X; while (M--) { int A, B, T; cin >> A >> B >> T; --A; --B; G[A].push_back(edge(B, T)); RG[B].push_back(edge(A, T)); } dijkstra(X); G = RG; memcpy(rd, d, sizeof(d)); dijkstra(X); for (int i = 0; i < V; ++i) { d[i] += rd[i]; } cout << *max_element(d, d + V) << endl; return 0;}用warshall_floyd的话会TLE，10003复杂度果然不是盖的.
http://www.cnblogs.com/Jason-Damon/archive/2012/04/29/2476285.html
2.SPFA
#define INF 0x7fffff int map[MAXN][MAXN]; int dist[MAXN]; bool vist[MAXN]; int queue[MAXN*MAXN]; int N,X,M; void SPFA() { int i; for(i=0; i<=N; i++) { dist[i]=INF; } memset(vist,false,sizeof(vist)); dist[X]=0; //初始化节点 queue[0]=X; int head=0,tail=1; while(head<tail) { int u=queue[head]; vist[u]=true; for(i=1; i<=N; i++) //更新从u出去的边 { if(map[u][i]!=INF && dist[i]>dist[u]+map[u][i]) { dist[i]=dist[u]+map[u][i]; if(!vist[i]) { vist[i]=true; queue[tail]=i; tail++; } } } vist[u]=false; //出队 head++; } } void Traverse() //make map[i][j]=map[j][i]; reverse the matrix { int i,j,tmp; for(i=1; i<=N; i++) { for(j=1; j<i; j++) { tmp=map[i][j]; map[i][j]=map[j][i]; map[j][i]=tmp; } } } int main() { int i,j,a,b,w,max[MAXN],result; freopen("acm.txt","r",stdin); scanf("%d%d%d",&N,&M,&X); for(i=1; i<=N; i++) { for(j=1; j<=N; j++) { map[i][j]=INF; } } memset(max,0,sizeof(max)); for(i=1; i<=M; i++) { scanf("%d%d%d",&a,&b,&w); map[a][b]=w; } SPFA(); for(i=1; i<=N; i++) { max[i]=dist[i]; } Traverse(); SPFA(); result=0; for(i=1; i<=N; i++) { if(result<max[i]+dist[i]) result=max[i]+dist[i]; } printf("%d\n",result); return 0; }
Read full article from 3268 -- Silver Cow Party
