poj 2485 Highways(简单题）

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define M 70000
 4 #define N 510
 5 int map[N][N],a[N],b[N];
 6 int n;
 7 int met()
 8 {
 9     int i,k,min;
10     k=1;
11     a[k]=0;
12     while(b[k]==0)
13     {
14         b[k]=1;
15         for(i=1;i<=n;i++)
16             if(b[i]==0&&a[i]>map[k][i])
17                 a[i]=map[k][i];
18         min=M;
19         for(i=1;i<=n;i++)
20             if(b[i]==0&&a[i]<min)
21             {
22                 min=a[i];
23                 k=i;
24             }
25     }
26 
27      min=0;
28         for(i=2;i<=n;i++)
29             if(min<a[i])
30                 min=a[i];
31     return min;
32 }
33 
34 
35 int main()
36 {
37     int i,j;
38     int x,y,z;
39     int t;
40     scanf("%d",&t);
41     while(t--)
42     {
43          scanf("%d",&n);    
44         for(i=1;i<=n;i++)
45         {
46             for(j=1;j<=n;j++)
47                 scanf("%d",&map[i][j]);
48         }
49         memset(a,9,sizeof(a));//将a[]数组值为最大
50         memset(b,0,sizeof(b));
51             printf("%d\n",met());
52     }
53 
54     return 0;
55 }

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define M 70000
 4 #define N 510
 5 int map[N][N],a[N],b[N];
 6 int n;
 7 int met()
 8 {
 9     int i,k,flag,min;
10     for(i=1;i<=n;i++)
11     {
12         a[i]=map[1][i];
13     }
14     b[1]=1;
15     while(1)
16     {
17         flag=1;min=M;
18         for(i=2;i<=n;i++)
19             if(b[i]==0&&a[i]<min)
20             {
21                 min=a[i];flag=0;
22                 k=i;
23             }
24             if(flag)
25                 break;
26             b[k]=1;
27             for(i=2;i<=n;i++)
28                 if(b[i]==0&&a[i]>map[k][i])
29                     a[i]=map[k][i];
30     }
31      min=0;
32         for(i=2;i<=n;i++)
33             if(min<a[i])

34                 min=a[i];
35     return min;
36 }
37 
38 
39 int main()
40 {
41     int i,j;
42     int x,y,z;
43     int t;
44     scanf("%d",&t);
45     while(t--)
46     {
47          scanf("%d",&n);    
48         for(i=1;i<=n;i++)
49         {
50             for(j=1;j<=n;j++)
51                 scanf("%d",&map[i][j]);
52         }
53         memset(a,9,sizeof(a));
54         memset(b,0,sizeof(b));
55             printf("%d\n",met());
56     }
57 
58     return 0;
59 }