POJ 2377 Bad Cowtractors （プリム法）

http://poj.org/problem?id=2377

　最大全域木を求める問題。
　なんとなくプリム法で解いてみました。

#include <vector>
#include <cstdio>
#include <algorithm>
#include <queue>
#include <iostream>
using namespace std;
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);++i)
#define rep(i,n) REP(i, 0, n)

typedef pair<int, int> pint;
const int INF = 1e9;
int maxcost[1000];
bool used[1000];
vector<pint> G[1000];
int main() {
    int N, M; scanf("%d%d", &N, &M);
    rep(i, M) {
        int a, b, c;
        scanf("%d%d%d", &a, &b, &c);
        --a; --b;
        G[a].push_back(pint(b, c));
        G[b].push_back(pint(a, c));
    }
    fill_n(maxcost, 1000, -1);
    maxcost[0] = 0;
    int ans = 0;
    priority_queue<pint> que;
    que.push(pint(0, 0));
    while(!que.empty()) {
        int cos = que.top().first, cv = que.top().second; que.pop();
        if(used[cv] || maxcost[cv] > cos) continue;
        used[cv] = true;
        ans += maxcost[cv];
//        cout << cv << ' ' << maxcost[cv] << endl;
        rep(k, G[cv].size()) {
            int nv = G[cv][k].first;
            if(used[nv]) continue;
            if(maxcost[nv] < G[cv][k].second) {
                maxcost[nv] = G[cv][k].second;
                que.push(pint(maxcost[nv], nv));
            }
        }
    }
    rep(i, N) if(maxcost[i] == -1) {
        puts("-1");
        return 0;
    }
    printf("%d\n", ans);
    return 0;
}

　蟻本に優先順位つきキューを使うとオーダーが落ちると書いてあったのでその通りに実装。見た目がダイクストラ法とほとんど変わらないところが面白い気がします。
　ただ、やや遅いうえ実装もクラスカル法のほうがかなり楽なのであまり使う機会はないかもしれません。