poj 2485 -- Highways

 1 /*======================================================================
 2  *           Author :   kevin
 3  *         Filename :   Highways.cpp
 4  *       Creat time :   2014-07-09 15:05
 5  *      Description :
 6 ========================================================================*/
 7 #include <iostream>
 8 #include <algorithm>
 9 #include <cstdio>
10 #include <cstring>
11 #include <queue>
12 #include <cmath>
13 #define clr(a,b) memset(a,b,sizeof(a))
14 #define M 600
15 #define INF 0x7f7f7f7f
16 using namespace std;
17 int c[M][M],dis[M];
18 int prim(int n)
19 {
20     bool vis[M];
21     int i,j,k,sum = 0;
22     for(i = 0; i < n; i++){
23         dis[i] = c[0][i];
24         vis[i] = false;
25     }
26     vis[0] = true;
27     for(i = 1; i < n; i++){
28         int _min = INF;
29         j = 0;
30         for(k = 0; k < n; k++){
31             if(_min > dis[k] && !vis[k]){
32                 _min = dis[k];
33                 j = k;
34             }
35         }
36         vis[j] = true;
37         if(sum < _min){
38             sum = _min;
39         }
40         for(k = 0; k < n; k++){
41             if(dis[k] > c[j][k] && !vis[k]){
42                 dis[k] = c[j][k];
43             }
44         }
45     }
46     return sum;
47 }
48 int main(int argc,char *argv[])
49 {
50     int cas,n,value;
51     scanf("%d",&cas);
52     while(cas--){
53         clr(c,0);
54         scanf("%d",&n);
55         for(int i = 0; i < n; i++){
56             for(int j = 0; j < n; j++){
57                 scanf("%d",&value);
58                 c[i][j] = value;
59             }
60         }
61         int ans = prim(n);
62         printf("%d\n",ans);
63     }
64     return 0;
65 }