AOJ2249 Road Construction

Road Construction | Aizu Online Judge
競技プログラミングをしばらくサボっていたので、リハビリがてら蟻本の練習問題を解いています。

問題概要

有向グラフ（辺は距離、建設コストを持つ）が与えられるので、頂点１から全頂点への最短距離が変わらないようにいくつか辺を削って、合計コストが最小になるようにする。

解法

　要するに、ダイクストラ法をして、使わなかった辺を削ればいいわけです。
　このとき、経路復元の要領で、ある頂点について、直前に通った辺のコストを持っておきましょう。　
　ちょっと説明が難しいんですが、ダイクストラ法が終わると全域木ができていて、それがこの「直前に通った辺」の集合になっているわけです。
　なのでこれを全部足せばいい、と。

#include <bits/stdc++.h>
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> state;
int main() {
    cin.tie(0); ios::sync_with_stdio(false);
    const int INF = 1.0e9;
    for(int N, M; cin >> N >> M && N;) {
        vector<vector<tuple<int, int, int>>> G(N);
        rep(i, M) {
            int u, v, d, c;
            cin >> u >> v >> d >> c;
            --u; --v;
            G[u].emplace_back(v, d, c);
            G[v].emplace_back(u, d, c);
        }
        vector<int> mdist(N, INF), preEcos(N, INF);
        mdist[0] = preEcos[0] = 0;
        priority_queue<state, vector<state>, greater<state>> que;
        que.emplace(0, 0);
        while(!que.empty()) {
            int dis, cur;
            tie(dis, cur) = que.top(); que.pop();
            if(mdist[cur] < dis) continue;
            for(const auto& e : G[cur]) {
                int nv, ndis, ncos;
                tie(nv, ndis, ncos) = e;
                if(mdist[nv] > dis + ndis) {
                    mdist[nv] = dis + ndis;
                    preEcos[nv] = ncos;
                    que.emplace(mdist[nv], nv);
                } else if(mdist[nv] == dis + ndis && preEcos[nv] > ncos)
                  preEcos[nv] = ncos;
            }
        }
        cout << accumulate(preEcos.begin(), preEcos.end(), 0) << endl;
    }
    return 0;
}

　本当はダイクストラ法は最短距離が確定した頂点から順に操作を行っていくので云々というところからきちんと説明できればいいのですが、無理でした。