Codeforces Round#24 A:Ring road

keyword

グラフ　有向グラフ　C++

概要

n個の都市と有向の辺があり、環状に繋がっている(向きは考慮しない)。各辺の向きを逆にするのに必要なコストが与えられる。任意の都市から別の任意の都市まで行けるようにするには最小でどれだけのコストが必要か求める問題。
コンテスト中は問題の読解に時間がかかった。理解した後も中々解法が思いつかなかったので別の問題に先に取りかかって、結局提出したのはコンテスト終了の20分前位。
修正後のサーキットは右回りか左回りしかないので両方試して見ればよい、ということには気づいたけど適切なデータ構造が思いつかない。set使って泥臭く実装して投げるもWA。サーキットの検出のループ回数が間違っていることに気づいたので訂正したらAC。
競技プログラミングだと実は無限ループってそんなに怖くない(エラーがちゃんと発見できるので)のだから、whileを使うべきだったなあ、と反省。

typedef pair<int, int> pi;

int main(){
    int i, j, a, b, c, n;
    cin >> n;
    map<int, set<pi> > g;
    REP(i,n){
        cin >> a >> b >> c;
        g[a].insert(MP(b,0));
        g[b].insert(MP(a,c));
    }
    int best = 1<<29, total = 0, cur, next;
    cur = 1;
    next = g[cur].begin()->fs;
    total += g[cur].begin()->sc;
    REP(i,n-1){
        EACH(g[next],it)if(it->fs != cur){
            cur = next;
            next = it->fs;
            total += it->sc;
            break;
        }
    }
    best = min(best, total);
    total = 0;
    cur = 1;
    next = g[cur].rbegin()->fs;
    total += g[cur].rbegin()->sc;
    REP(i,n-1){
        EACH(g[next],it)if(it->fs != cur){
            cur = next;
            next = it->fs;
            total += it->sc;
            break;
        }
    }
    best = min(best, total);
    cout << best << endl;
    return 0;
}