poj 1125 谣言传播 Floyd 模板题

本文主要是介绍poj 1125 谣言传播 Floyd 模板题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

假如有3个点点1到点2要5分钟点1到点3要3分钟那么5分钟的时间可以传遍全图所以要先找一个点到其他点的最长时间再从最长的时间里找出最小值

Sample Input

3 // 结点数
2 2 4 3 5 //点1与另外2个点相连 1->2 权值为4 1->3 权值为5
2 1 2 3 6 //点2与...
2 1 2 2 2//点3...
5
3 4 4 2 8 5 3
1 5 8
4 1 6 4 10 2 7 5 2
0
2 2 5 1 5
0
Sample Output

3 2
3 10

 1 # include <iostream>
 2 # include <cstdio>
 3 # include <cstring>
 4 # include <string>
 5 # include <algorithm>
 6 # include <cmath>
 7 # include <map>
 8 # define LL long long
 9 using namespace std ;
10 
11 const int MAXN = 110 ;
12 const int INF = 0x3f3f3f3f;
13 int dis[MAXN][MAXN];
14 int n ;
15 
16 void floyed()//节点从1~n编号
17 {
18     int i,j,k;
19     for(k=1;k<=n;k++)
20        for(i=1;i<=n;i++)
21          for(j=1;j<=n;j++)
22              if(dis[i][k]+dis[k][j] < dis[i][j])
23                  dis[i][j]=dis[i][k]+dis[k][j];
24 
25 }
26 
27 int main()
28 {
29     //freopen("in.txt","r",stdin) ;
30     while (scanf("%d" , &n) , n)
31     {
32         int i , j ;
33         for(i=1;i<=n;i++)
34           for(j=1;j<=n;j++)
35           {
36               if(i==j)dis[i][j]=0;
37               else dis[i][j]=INF;
38           }
39         int m ,v ,w ;
40         for(i=1;i<=n;i++)
41         {
42             scanf("%d" , &m) ;
43             while(m--)
44             {
45                 scanf("%d %d" , &v , &w) ;
46                 if (w < dis[i][v])
47                     dis[i][v] = w ;
48             }
49         }
50         floyed() ;
51         int ans = INF ;
52         int k ;
53         for(i=1;i<=n;i++)
54         {
55             int t = 0 ;
56             for(j=1;j<=n;j++)
57             {
58                 if (i != j && dis[i][j] > t)
59                 {
60                     t = dis[i][j] ;
61                 }
62             }
63             if (t < ans)
64             {
65                 ans = t ;
66                 k = i ;
67             }
68         }
69         if (ans != INF)
70            printf("%d %d\n" , k , ans) ;
71         else
72            printf("disjoint\n") ;
73     }
74     return 0;
75 }