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
" , k , ans) ;
71         else
72            printf("disjoint
") ;
73     }
74     return 0;
75 }

View Code