AOJ 2249 Road Construction - mayoko’s diary

問題

連結な無向グラフが与えられる。各辺には長さとコストが定義されている。このグラフを次の条件を満たすように変更したい。

各点 v の 0 からの距離(距離は辺の長さで定義される)が元のグラフと変わらない。
任意の点の組 (v, u) は連結(この条件いらない気がする)

上記の条件を満たすもとで, グラフの辺のコストの和を最小化したい。最小化した時のコストの和を求めよ。

解法

まずダイクストラして各点の最短距離を求めます。

各点 v の最短距離を d[v] とすると, v から出ているある辺 e が存在して, d[v] = d[e.u] + e.d (e.u は e の行き先, e.d は e の長さ)となっているはずです(最短距離はどこかの点から移動するのが原因になっているはずだから)。

このような条件を満たす辺のうち, 最小コストのものを貪欲に選ぶ, ということをやれば, 最短距離性は保証されたままコスト最小のものを選べます。

struct edge {
    int v;
    ll w;
    ll cost;
    edge() {}
    edge(int v, ll w, ll cost) : v(v), w(w), cost(cost) {};
};

vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) {
    vector<ll> d(n, LLONG_MAX/10); d[s] = 0;
    priority_queue<pair<ll, int> > que;
    que.push(make_pair(0ll, s));
    while (!que.empty()) {
        auto p = que.top(); que.pop();
        int u = p.second;
        ll dist = -p.first;
        if (dist > d[u]) continue;
        for (edge e : G[u]) {
            if (d[e.v] > d[u]+e.w) {
                d[e.v] = d[u] + e.w;
                que.push(make_pair(-d[e.v], e.v));
            }
        }
    }
    return d;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    int N, M;
    while (cin >> N >> M) {
        if (N==0 && M==0) break;
        vector<vector<edge> > G(N);
        while (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);
        }
        auto dist = dijkstra(N, G, 0);
        ll ans = 0;
        for (int i = 1; i < N; i++) {
            ll mini = 101010;
            for (edge e : G[i]) {
                if (dist[i] == dist[e.v]+e.w) {
                    mini = min(mini, e.cost);
                }
            }
            ans += mini;
        }
        cout << ans << endl;
    }
    return 0;
}

この問題の解法思いついた背景なんですが, 大学歩いてたら sugim さん見かけて, そしたらパッと思いつきました。ありがたや。