Highways
9040 ワード
http://poj.org/problem?id=2485
View Code
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