poj1258（Agri-net）

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <sstream>
 4 #include <cstdlib>
 5 #include <cstring>
 6 #include <cstdio>
 7 #include <string>
 8 #include <bitset>
 9 #include <vector>
10 #include <queue>
11 #include <stack>
12 #include <cmath>
13 #include <list>
14 //#include <map>
15 #include <set>
16 using namespace std;
17 /***************************************/
18 #define ll long long
19 #define int64 __int64
20 /***************************************/
21 const int INF = 0x7f7f7f7f;
22 const double eps = 1e-8;
23 const double PIE=acos(-1.0);
24 const int d1x[]= {0,-1,0,1};
25 const int d1y[]= {-1,0,1,0};
26 const int d2x[]= {0,-1,0,1};
27 const int d2y[]= {1,0,-1,0};
28 const int fx[]= {-1,-1,-1,0,0,1,1,1};
29 const int fy[]= {-1,0,1,-1,1,-1,0,1};
30 /***************************************/
31 void openfile()
32 {
33     freopen("data.in","rb",stdin);
34     freopen("data.out","wb",stdout);
35 }
36 /**********************华丽丽的分割线,以上为模板部分*****************/
37 #define N 600
38 int map[N][N];
39 int lowcost[N];
40 int vis[N];
41 int n;
42 int ce;
43 int maax;
44 int dijstra()
45 {
46     int i,j,k=0;
47     int cnt=0;
48     int min;
49     for(i=1; i<=n; i++)
50     {
51         lowcost[i]=map[1][i];
52         vis[i]=0;
53     }
54     vis[1]=1;
55     for(i=1; i<n; i++)
56     {
57         min=INF;
58         for(j=1; j<=n; j++)
59         {
60             if (!vis[j]&&lowcost[j]<min)
61             {
62                  min=lowcost[j];
63                  k=j;
64             }
65         }
66         vis[k]=1;
67         cnt+=min;
68         for(j=1;j<=n;j++)
69             if(!vis[j]&&lowcost[j]>map[k][j])
70                 lowcost[j]=map[k][j];
71     }
72     return cnt;
73 }
74 int main()
75 {
76    // int cas;
77    // scanf("%d",&cas);
78     while(scanf("%d",&n)!=EOF)
79     {
80         int i,j;
81         for(i=0;i<=N;i++)
82             for(j=0;j<=N;j++)
83                 map[i][j]=INF;
84         int x;
85         for(i=1;i<=n;i++)
86         {
87             for(j=1;j<=n;j++)
88             {
89                 scanf("%d",&x);
90                 map[i][j]=x;
91             }
92         }
93         maax=dijstra();
94         printf("%d\n",maax);
95     }
96     return 0;
97 }