Posted on 2008-03-29 17:18
superman 閱讀(192)
評論(0) 編輯 收藏 引用 所屬分類:
ZOJ
1 /* Accepted 1082 C++ 00:00.00 872K */
2 #include <limits.h>
3 #include <iostream>
4
5 using namespace std;
6
7 int main()
8 {
9 int n;
10 while((cin >> n) && n)
11 {
12 unsigned dist[101][101];
13 memset(dist, 0XFF, sizeof(dist));
14
15 int s, t, m;
16 for(s = 1; s <= n; s++)
17 {
18 cin >> m;
19 while(m--)
20 {
21 cin >> t;
22 cin >> dist[s][t];
23 }
24 }
25
26 for(int k = 1; k <= n; k++)
27 for(int i = 1; i <= n; i++)
28 for(int j = 1; j <= n; j++)
29 if(i != j && dist[i][k] != UINT_MAX && dist[k][j] != UINT_MAX)
30 dist[i][j] <?= dist[i][k] + dist[k][j];
31
32 int min = INT_MAX;
33 for(int i = 1; i <= n; i++)
34 {
35 int max = 0;
36 bool flag = 1;
37 for(int j = 1; j <= n; j++)
38 if(i != j)
39 {
40 if(dist[i][j] != UINT_MAX)
41 max >?= dist[i][j];
42 else
43 {
44 flag = 0;
45 break;
46 }
47 }
48 if(flag)
49 if(min > max)
50 {
51 min = max;
52 s = i;
53 }
54 }
55
56 if(min == INT_MAX)
57 cout << "disjoint" << endl;
58 else
59 cout << s << ' ' << min << endl;
60 }
61
62 return 0;
63 }
64