AOJ 0072 Carden Lantern
方針
最小全域木問題。
プリム法で解いています
蟻本と一緒です。
const int INF = 1 << 30; int cost[100][100]; int mincost[100]; bool used[100]; int V; int prim() { int res = 0; mincost[0] = 0; while(1) { int v = -1; for(int u = 0; u < V; u++) if(!used[u] && (v == -1 || mincost[u] < mincost[v])) v = u; if(v == -1) break; used[v] = true; res += mincost[v]; for(int u = 0; u < V; u++) mincost[u] = min(mincost[u], cost[v][u]); } return res; } int main() { int m; while(scanf("%d", &V), V) { scanf("%d", &m); fill(mincost, mincost + V, INF); fill(used, used + V, false); for(int i = 0; i < V; i++) fill(cost[i], cost[i] + V, INF); for(int i = 0; i < m; i++) { int from, to, dist; scanf("%d,%d,%d", &from, &to, &dist); dist /= 100, dist -= 1; cost[from][to] = dist; cost[to][from] = dist; } printf("%d\n", prim()); } }