【POJ】1287 Networking

 1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 using namespace std; 5 const int maxn = 55; 6 const int inf = 0x3f3f3f3f; 7 int mp[maxn][maxn]; 8 int dis[maxn]; 9 bool vis[maxn];10 int n,m;11 int prim(){12 ????memset(dis,0x3f,sizeof(dis));13 ????memset(vis,0,sizeof(vis)); 14 ????int ans = 0;15 ????dis[1] = 0;16 ????while(1){17 ????????int k = 0;18 ????????for(int j = 1; j <= n;j++){19 ????????????if(!vis[j] && dis[j] < dis[k])20 ????????????????k = j; 21 ????????} 22 ????????if(!k) break;23 ????????vis[k] = 1; 24 ????????ans += dis[k];25 ????????for(int j = 1; j <= n;j++){26 ????????????if(dis[j] > mp[k][j]){27 ????????????????dis[j] = mp[k][j];28 ????????????}29 30 ????????}31 ????}32 ????return ans;33 }34 35 36 int main(){37 ????while(cin>>n && n){38 ????????memset(mp,0x3f,sizeof(mp)); 39 ????????cin>>m;40 ????????if(m == 0){41 ????????????cout<<0<<endl;42 ????????????continue;43 ????????}44 ????????while(m--){45 ????????????int x,y,w;46 ????????????cin>>x>>y>>w;47 ????????????mp[x][y] = mp[y][x] = min(mp[x][y],w);48 ????????}49 ????????cout<<prim()<<endl;50 ????}51 52 ????return 0;53 }