AOJ 0180 - Stellar Performance of the Debunkey Family(Prim法)
タイトルがながい
#include<iostream> #include<algorithm> const int MAX_N = 100, MAX_M = 100, INF = 1 << 24; int n, m; int cost[MAX_N][MAX_N], mincost[MAX_N], used[MAX_N]; int prim(){ std::fill(mincost, mincost+MAX_N, INF); std::fill(used, used+MAX_N, 0); mincost[0] = 0; int res = 0; while(true){ int v = -1; for(int i=0;i<n;i++){ if(!used[i] && (v == -1 || mincost[i] < mincost[v])){ v = i; } } if(v == -1){ break; } used[v] = 1; res += mincost[v]; for(int i=0;i<n;i++){ mincost[i] = std::min(mincost[i], cost[v][i]); } } return res; } int main(){ while(std::cin >> n >> m, n){ for(int i=0;i<MAX_N;i++){ std::fill(cost[i], cost[i]+MAX_N, INF); } for(int i=0;i<m;i++){ int a, b, c; std::cin >> a >> b >> c; cost[a][b] = c; cost[b][a] = c; } std::cout << prim() << std::endl; } }