Highways

 1 #include<cstdio>
 2  #include<cstring>
 3  #include<algorithm>
 4  #define MAXN 2010
 5  
 6  const int INF=1<<28;
 7  using namespace std;
 8  int g[MAXN][MAXN];
 9  int dis[MAXN];
10  bool vis[MAXN];
11  int n,sum,max1;
12  bool sprim()
13  {
14      memset(vis,false,sizeof(vis));
15      for(int i=1;i<=n;i++)
16          dis[i]=INF;
17      dis[1]=0;sum=0,max1=-1;
18      for(int i=1;i<=n;i++)
19      {
20          int min=INF,k=0;
21          for(int j=1;j<=n;j++)
22          {
23              if(!vis[j]&&dis[j]<min)
24              {
25                  min=dis[j];
26                  k=j;
27              }
28          }
29          if(min==INF) return false;
30          vis[k]=true;
31          if(min>max1)
32          {
33              max1=min;
34          }
35          for(int j=1;j<=n;j++)
36          {
37              if(!vis[j]&&dis[j]>g[k][j])
38              {
39                  dis[j]=g[k][j];
40              }
41          }
42      }
43      printf("%d
",max1);
44      return true;
45  }
46  int main()
47  {
48       int t=0;
49       scanf("%d",&t);
50       while(t--){
51           scanf("%d",&n);
52         for(int i=1;i<=n;i++)
53         {
54             for(int j=1;j<=n;j++)
55             {
56                 scanf("%d",&g[i][j]);
57             }
58         }
59         sprim();
60       }
61      return 0;
62  
63  }
64
View Code