POJ1258Agri-Net（prime基础）

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