1 /*
 2     最短路：Floyd模板题
 3             主要是两点最短的距离和起始位置
 4     http://blog.csdn.net/y990041769/article/details/37955253
 5 */
 6 #include <cstdio>
 7 #include <iostream>
 8 #include <algorithm>
 9 #include <cmath>
10 #include <cstring>
11 #include <string>
12 #include <vector>
13 using namespace std;
14 
15 const int MAXN = 100 + 10;
16 const int INF = 0x3f3f3f3f;
17 int d[MAXN][MAXN];
18 
19 void Floyd_Warshall(int n)
20 {
21     for (int k=1; k<=n; ++k)
22     {
23         for (int i=1; i<=n; ++i)
24         {
25             for (int j=1; j<=n; ++j)
26             {
27                 if (d[i][j] > d[i][k] + d[k][j])
28                     d[i][j] = d[i][k] + d[k][j];
29             }
30         }
31     }
32 }
33 
34 void work(int n)
35 {
36     Floyd_Warshall (n);
37     int res;   int ans = INF;  int num;
38     for (int i=1; i<=n; ++i)
39     {
40         res = 0;
41         for (int j=1; j<=n; ++j)
42         {
43             if (i == j) continue;
44             if (res < d[i][j])  res = d[i][j];
45         }
46         if (ans > res)
47         {
48             ans = res;
49             num = i;
50         }
51     }
52 
53     printf ("%d %d\n", num, ans);
54 }
55 
56 int main(void)      //POJ 1125  Stockbroker Grapevine
57 {
58     //freopen ("E.in", "r", stdin);
59 
60     int n, m;
61     while (~scanf ("%d", &n) && n)
62     {
63         for (int i=1; i<=n; ++i)
64             for (int j=1; j<=n; ++j)    d[i][j] = INF;
65         for (int i=1; i<=n; ++i)
66         {
67             scanf ("%d", &m);
68             int x, y;
69             for (int j=1; j<=m; ++j)
70             {
71                 scanf ("%d%d", &x, &y);
72                 d[i][x] = y;
73             }
74         }
75 
76         work (n);
77     }
78 
79     return 0;
80 }

优质内容筛选与推荐>>
1、OOD沉思录 --- 导引
2、从入口文件找到Vue构造函数
3、【001】学习计划 - 开始学习C#，用C#
4、WCF问题:“HTTP 错误 404.17 - Not Found 请求的内容似乎是脚本，因而将无法由静态文件处理程序来处理”解决方法
5、DOM常用对象