sicily 1090 Highways

 1 #include <cstdio>
 2 #include <cstring>
 3 #include <algorithm>
 4 using namespace std;
 5 
 6 const int INF=0x3f3f3f3f;
 7 int map[505][505];
 8 int visit[505];
 9 int dis[505];
10 int ans[505];
11 
12 //最小生成树 
13 int prim(int n, int cur) //从哪个点开始都可以 
14 {
15     memset(ans, 0, sizeof(ans));
16     visit[cur] = 1;
17     int index;
18     int count=0;
19     for(int i=1; i<=n; i++)
20         dis[i] = map[cur][i]; //dis[i]为到每个相邻顶点的最小距离 
21     
22     for(int i=2; i<=n; i++)
23     {
24         int minn = 0x3f3f3f3f;
25         for(int j=1; j<=n; j++)
26         {
27             if(!visit[j] && dis[j] < minn)
28             {
29                 minn = dis[j];
30                 index = j;
31             } 
32         }
33         visit[index] = 1;
34         ans[count++] = minn;
35         
36         for(int j=1; j<=n; j++)
37             if(!visit[j] && dis[j] > map[index][j])
38                 dis[j] = map[index][j];
39     }
40     return count;
41 }
42 
43 int main()
44 {
45     int t, n;
46     scanf("%d", &t);
47     int k=0;
48     while(t--)
49     {
50         if(k==0)
51             k++;
52         else
53             printf("\n");
54         memset(dis, 0, sizeof(dis));
55         memset(map, 0, sizeof(map));
56         memset(visit, 0, sizeof(visit));
57         
58         scanf("%d", &n);
59         for(int i=1; i<=n; i++)
60             for(int j=1; j<=n; j++)
61             {
62                 map[i][j] = INF; 
63                 scanf("%d", &map[i][j]);
64             }
65         int cnt = prim(n, 1);
66         sort(ans, ans+cnt);
67         printf("%d\n", ans[cnt-1]);
68     }
69     return 0;
70 }