問題:
http://acm.pku.edu.cn/JudgeOnline/problem?id=1125思路:
題意還是蠻簡單的，第一次寫Floyd-Warshall算法求每對頂點間的最短距離
代碼:
1 /* Floyd-Warshall algorithm */
2 #include<stdio.h>
3 #include<stdlib.h>
4 #include<string.h>
5 #define MAX_N 101
6 #define INF 0x7FFFFFFF
7 #define Min(a,b) ((a)<(b) ? (a) : (b))
8 #define Max(a,b) ((a)<(b) ? (b) : (a))
9 int weight[MAX_N][MAX_N];
10 int d[MAX_N][MAX_N];
11 int max[MAX_N];
12 int n;
13
14 void
15 init()
16 {
17 int i, j, cnt, t, c;
18 memset(weight, 0, sizeof(weight));
19 for(i=1; i<=n; i++) {
20 scanf("%d", &cnt);
21 for(j=0; j<cnt; j++) {
22 scanf("%d %d", &t, &c);
23 weight[i][t] = c;
24 }
25 }
26 }
27
28 void
29 floyd_warshall() /* O(n^3) */
30 {
31 int i, j, k;
32 for(i=1; i<=n; i++)
33 for(j=1; j<=n; j++)
34 d[i][j] = (i==j?0:INF);
35 for(i=1; i<=n; i++)
36 for(j=1; j<=n; j++)
37 if(weight[i][j])
38 d[i][j] = weight[i][j];
39 for(k=1; k<=n; k++) {
40 for(i=1; i<=n; i++) {
41 for(j=1; j<=n; j++) {
42 if(d[i][k]!=INF && d[k][j]!=INF)
43 d[i][j] = Min(d[i][j], d[i][k]+d[k][j]);
44 }
45 }
46 }
47 }
48
49 void
50 output()
51 {
52 int i, j, p, rt;
53 memset(max, 0, sizeof(max));
54 rt = INF;
55 for(i=1; i<=n; i++) {
56 for(j=1; j<=n; j++)
57 if(i!=j) {
58 max[i] = Max(max[i], d[i][j]);
59 }
60 if(max[i] < rt) {
61 rt = max[i];
62 p = i;
63 }
64 }
65 if(rt == INF)
66 printf("disjoint\n");
67 else
68 printf("%d %d\n", p, rt);
69 }
70
71 int
72 main(int argc, char **argv)
73 {
74 while(scanf("%d", &n)!=EOF && n) {
75 init();
76 floyd_warshall();
77 output();
78 }
79 }