최 단 로 (Floyd Warshall) POJ 1125 Stockbroker Grapevine

제목 전송 문

 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
", 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 }