POJ2485Highways（prime 水题）

 1 #include <iostream>
 2 #include <cstdio>
 3 #include <algorithm>
 4 #include <cstring>
 5 #include <string.h>
 6 using namespace std;
 7 const int INF = 10000000;
 8 const int MAX = 500 + 10;
 9 int g[MAX][MAX],vis[MAX],dist[MAX];
10 
11 int main()
12 {
13     int n,t;
14     scanf("%d", &t);
15     while(t--)
16     {
17         scanf("%d", &n);
18         for(int i = 1; i <= n; i++)
19         {
20             for(int j = 1; j <= n; j++)
21             {
22                 scanf("%d", &g[i][j]);
23             }
24         }
25         memset(dist,0,sizeof(dist));
26         memset(vis,0,sizeof(vis));
27         for(int i = 2; i <= n; i++)
28             dist[i] = g[1][i];
29         vis[1] = 1;
30         int ans = 0;
31         for(int i = 1; i < n; i++)
32         {
33             int minn = INF,pos;
34             for(int j = 1; j <= n; j++)
35             {
36                 if(vis[j] == 0 && dist[j] < minn)
37                 {
38                     pos = j;
39                     minn = dist[j];
40                 }
41             }
42             ans = max(ans,minn);
43             vis[pos] = 1;
44             for(int j = 1; j <= n; j++)
45             {
46                 dist[j] = min(dist[j],g[pos][j]);
47             }
48         }
49         printf("%d\n",ans);
50     }
51 
52     return 0;
53 }