题意：很多牛（在各自的farm）去某个farm聚会，聚会结束后返回（不是原路，路是单向的），要时间最短。
求 这些牛所用时间最长的那个要多长时间？返回的时候，以聚会的farm为起点，单源最短路径问题；
来时，可以想象成路径反向，从聚会的farm的单源最短路径问题。当然我处理时，往返 过程反着处理了。
两次dijkstra,第二次把路径反向。
代码：
View Code
1 #include<cstdio>
2 #include<cstdlib>
3 #include<cstring>
4 #define MAX 0x7fffff
5 using namespace std;
6
7 /*
8 题目最大范围1000，开到1001，WA到吐血。
9 一狠心开到1010，AC了。
10 可见，POJ 有多贱 ！
11 */
12 const int N = 1010;
13 int farm[N][N];
14 int dis[N],d[N];
15 bool flag[N];
16
17 int f,route;
18
19 void dijkstra(int s);
20 void reverse(int a[N][N]);
21
22 int main()
23 {
24 int i,j,ans,x,y,t,start;
25 scanf("%d%d%d",&f,&route,&start);
26 for(i = 1 ; i <= f ; ++i)
27 for(j = 1 ; j < i ; ++j)
28 farm[i][j] = farm[j][i] = MAX;
29
30 for(i = 1 ; i <= f ; ++i)
31 farm[i][i] = 0;
32
33 for( i = 0 ;i < route ; ++i)
34 {
35 scanf("%d%d%d",&x,&y,&t);
36 if(t<farm[x][y])
37 farm[x][y] = t;
38 }
39
40 dijkstra(start);
41
42 for(i = 1 ; i <= f; ++i)
43 d[i] = dis[i];
44
45 reverse(farm);//矩阵转置
46 dijkstra(start);
47
48 ans = 0;
49
50 for(i = 1 ; i <= f ; ++i)
51 {
52 d[i] += dis[i];
53 if(d[i] > ans)
54 ans = d[i];
55 }
56
57 printf("%d\n",ans);
58 //system("pause");
59 return 0;
60 }
61
62 void dijkstra(int s)
63 {
64 int i,j,k,u,temp;
65 for(i = 1 ; i <= f; ++i )
66 {
67 dis[i] = farm[s][i] ;
68 flag[i] = false;
69 }
70
71 flag[s] = true;//起点进入最短路径集合
72
73 for(k = 1 ; k < f ; ++k)
74 {
75 temp = MAX;
76 for(i = 1 ; i <= f ; ++i)
77 if(!flag[i] && dis[i] < temp)//找出离起点最近的点
78 {
79 temp = dis[i];
80 u = i;
81 }
82 // printf("iimm\n");
83 flag[u] = true;//进入最短路径集合
84
85 for(i = 1 ; i <= f ; ++i)//刷新还没有进入集合的点
86 if(!flag[i]&& farm[u][i] != MAX && dis[i] > farm[u][i] + dis[u])
87 dis[i] = farm[u][i] + dis[u];
88 }//for(k)
89
90 }
91
92 void reverse(int a[N][N])
93 {
94 int i,j,t;
95 for(i = 1 ; i <= N ; ++i)
96 for(j = 1 ; j < i ; ++j)
97 {
98 t = a[i][j];
99 a[i][j] = a[j][i];
100 a[j][i] = t;
101 }
102 }