メモ

自分に向けて書いたメモを取り扱っています.

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());
    }
}