Stockbroker Grapevine

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 #define MAXN 110
 6 using namespace std;
 7 const int INF=1<<28;
 8 int dis[MAXN][MAXN];
 9 int n,t,a,b;
10 void inti()
11 {
12     for(int i=1; i<=n; i++)
13     {
14         for(int j=1; j<=n; j++)
15         {
16             dis[i][j]=dis[j][i]=INF;
17         }
18     }
19 }
20 int main()
21 {
22     while(scanf("%d",&n)&&n)
23     {
24         inti();
25         for(int i=1; i<=n; i++)
26         {
27             scanf("%d",&t);
28             while(t--)
29             {
30                 scanf("%d%d",&a,&b);
31                 dis[i][a]=b;
32             }
33         }
34         for(int k=1; k<=n; k++)
35         {
36             for(int i=1; i<=n; i++)
37             {
38                 for(int j=1; j<=n; j++)
39                 {
40                     dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
41                 }
42             }
43         }
44         int cc,tt=-1,mark=1;
45         for(int i=1; i<=n; i++)
46         {
47             int t=-1,c;
48             bool flag=true;
49             for(int j=1; j<=n; j++)
50             {
51                 if(i!=j)
52                 {
53                     if(dis[i][j]==INF)
54                     {
55                         flag=false;
56                         break;
57                     }
58                     else if(dis[i][j]>t)
59                     {
60                         c=i;
61                         t=dis[i][j];
62                     }
63                 }
64                 else continue;
65             }
66             if(flag)
67             {
68                 if(mark)
69                 {
70                     cc=c;
71                     tt=t;
72                     mark=0;
73                 }
74                 else if(t<tt)
75                 {
76                     cc=c;
77                     tt=t;
78                 }
79             }
80         }
81         if(tt==-1) printf("disjoint
");
82         else printf("%d %d
",cc,tt);
83     }
84     return 0;
85 }
View Code