AOJ 0324 Downhill Race

問題文

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=0324

解法

ダイクストラで解く．
与えられるグラフはDAGになっていて，この上で2回違う条件で最短経路を求めたい．しかし依存関係にあるので独立にはできない．
こういうときは1回目と2回めを同時に処理するのが定番な気がするので，それで考えてみる．つまり，2つの頂点を同時に持つようにする．
そしてこれもある意味定番なのだが，これらの2つの頂点ないし遷移は，ある規則によって順序付けられるようにすると良い．
今回であればトポロジカル順序を利用する．

dist[fst_v][sec_v] := 1回目の経路の末端が頂点 fst_v であり，2回目の経路の末端が頂点 sec_v であるときの最小コスト

とする．

fst_v == sec_v のときの遷移は，以下の2パターンがある．

• 同じ辺を使って移動する．
• 違う辺を使って移動する（今回は多重辺がないので違う頂点へ移動する）．

辺のコスト t2 を使うのはこの1つ目の場合である．

次に，fst_v != sec_v のときを考える．これは先に述べたトポロジカル順序に則って遷移させる．
トポロジカル順序で fst_v < sec_v のとき，fst_v を先に遷移させる．このとき，遷移時の辺のコストは t1 としてよい．
逆に fst_v > sec_v のときは，sec_v を先に遷移させる．

これでうまくいく．トポロジカル順序で小さい方を先に移動させることで，1回目と2回目の最短経路で t1 を2度使うことはなくなる．
一応示しておく．もし t1 を2回使ってしまうような状況に陥るとしたら，1回めと2回目の経路で共通の頂点を用い，かつそこからの行き先が同じような経路をもつ場合である．
トポロジカル順序で小さい方を先に処理した場合，共通の頂点を使うならば，かならず fst_v == sec_v で処理されるようになる．このときは場合分けしているので t1 を2回使うことはない．
逆に言うとこうしないと t1 を2回使いうる．例えば，共通頂点が v3 として (v1, v2) -> (v3, v2) -> (v4, v2) -> (v4, v3) のように遷移すると，最後の v2 -> v3 のコストでどちらを使えばいいかわからなくなってしまう．

計算量は O( (N^2 + P^2) log N ) となる．

ソースコード

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

constexpr ll inf = 1e18;

struct edge {
    int to;
    ll c1, c2;
};

using edges = vector<edge>;
using graph = vector<edges>;

int main() {
    int n, p;
    cin >> n >> p;
    graph g(n);
    for(int i = 0; i < p; ++i) {
        int s, e;
        ll t1, t2;
        cin >> s >> e >> t1 >> t2;
        g[s - 1].push_back(edge{e - 1, t1, t2});
    }

    vector<int> topo(n, -1);
    int idx = 0;
    function<void(int)> calc_topo = [&] (int v) {
        if(topo[v] != -1) return;
        for(auto& e : g[v]) {
            calc_topo(e.to);
        }
        topo[v] = idx++;
    };
    calc_topo(0);

    vector<vector<ll>> dist(n, vector<ll>(n, inf));
    dist[0][0] = 0;
    using state = tuple<ll, int, int>;
    priority_queue<state, vector<state>, greater<state>> que;
    que.emplace(0, 0, 0);
    while(!que.empty()) {
        ll cur_c;
        int fst_v, sec_v;
        tie(cur_c, fst_v, sec_v) = que.top();
        que.pop();
        if(fst_v == sec_v) {
            for(auto& e : g[fst_v]) {
                ll nxt_c = cur_c + e.c1 + e.c2;
                if(dist[e.to][e.to] > nxt_c) {
                    dist[e.to][e.to] = nxt_c;
                    que.emplace(nxt_c, e.to, e.to);
                }
            }

            for(auto& e1 : g[fst_v]) {
                for(auto& e2 : g[sec_v]) {
                    if(e1.to == e2.to) continue;
                    ll nxt_c = cur_c + e1.c1 + e2.c1;
                    if(dist[e1.to][e2.to] > nxt_c) {
                        dist[e1.to][e2.to] = nxt_c;
                        que.emplace(nxt_c, e1.to, e2.to);
                    }
                }
            }
        } else {
            if(topo[fst_v] > topo[sec_v]) {
                for(auto& e : g[fst_v]) {
                    ll nxt_c = cur_c + e.c1;
                    if(dist[e.to][sec_v] > nxt_c) {
                        dist[e.to][sec_v] = nxt_c;
                        que.emplace(nxt_c, e.to, sec_v);
                    }
                }
            } else {
                for(auto& e : g[sec_v]) {
                    ll nxt_c = cur_c + e.c1;
                    if(dist[fst_v][e.to] > nxt_c) {
                        dist[fst_v][e.to] = nxt_c;
                        que.emplace(nxt_c, fst_v, e.to);
                    }
                }
            }
        }
    }

    cout << dist[n - 1][n - 1] << endl;
}

感想

トポロジカル順序で小さい方から遷移するときに，遷移先がもう一方の頂点より大きくないとだめ，みたいなよくわからない処理を書いて（なぜ？）WAを食らってしまった．
他にも最小費用流とか生えそうな見た目をしているけど，経験的に1回め流れるときと2回め流れるときでコストを分けるみたいなフローは書くのが難しいと思う．解けるのかな？
最後に類題を貼り付けておきます．
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1324

ちなみにこの問題ダイクストラで解きましたがDAGなので普通に DP で良いと思う．log が取れるので定数倍しんどいときは DP で解くべき．