AOJ 0180 Stellar Performance of the Debunkey Family

方針

最小全域木。
AOJ 0072 Carden Lantern - Allen' Memoと一緒です。

const int INF = 1 << 30;

int V;
int cost[100][100];
int mincost[100];
bool used[100];

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;

        res += mincost[v];
        used[v] = true;

        for(int u = 0; u < V; u++)
            mincost[u] = min(mincost[u], cost[u][v]);
    }

    return res;
}

int main()
{
    int m;

    while(scanf("%d%d", &V, &m), V|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);

            cost[from][to] = cost[to][from] = dist;
        }

        printf("%d\n", prim());
    }
}