模擬国内2010D Mr. リトー郵便局 (AOJ2200)

解けてうれしかったので書きました。新規性は無いです。

問題概要

onlinejudge.u-aizu.ac.jp

頂点辺の無向グラフがある。無向グラフの各辺は「陸路」か「海路」であり、海路である辺は船が無いと利用することができない。陸路はそのような制限は無いが、船をもっている状態で陸路を移動する場合、船は移動前の頂点に置いていくことになる。それぞれの辺には非負整数の重みがある。

要素の数列を与える。あなたは一隻船をもった状態で頂点にいる。船はこれ以外に存在しない。この状態からをこの順に含むような移動の方法で(連続で含んでいる必要は無い)、通った辺の重みの最小値を求めよ。

制約

• 

• 

• 

• それぞれの辺のコストは以上以下

• 条件を満たす(を部分列に含む)移動の方法が存在する

• 多重辺が存在するかもしれない。

• 入力は複数のテストケースで構成される

• メモリ制限: KB

• TL: sec

TLE解

辺が非負重みの最短経路問題なので、ダイクストラ法で解くことを考えます。海路が使えるかどうかと、の前から何要素を移動経路に含んだかの状態が欲しいので、以下のように状態を持った頂点を考えます。

・・・元のグラフで頂点がで、船が頂点にあって、現在までの移動経路にを前から要素を含んでいる。

このような状態を持った状態で新しくグラフを構築します。辺は以下のように張ります。

• 元のグラフでコストの陸路がある についてとを結ぶコストの無向辺を張る

• 元のグラフでコストの海路がある についてとを結ぶコストの無向辺を張る

• 、についてからへのコストの有向辺を張る。

始点はとしてダイクストラ法を適用し、である頂点への最短経路コストのが解になります。

• のの方の頂点倍加はAtCoder社長が汎用テクみたいな感じでTwitterでつぶやいていた気がします。

このグラフの大きさは、雑に見積もっても頂点数、辺数です。辺数がだいぶ厳しいことになっています。(複数テストケースなので、8secでも厳しいと思います。試してないけど...)

高速化

最短経路について、頂点から頂点へどのような移動をするかを考えます。

陸路のみを使う時・・・頂点から頂点へ陸路のみで最短で移動する

海路を利用する時・・・頂点から船がある頂点まで陸路のみで最短で移動する-> 海路のみを利用して船がある頂点から頂点まで最短で移動する-> 頂点から頂点で陸路のみで最短で移動する

• はを満たすどれか

それぞれの移動をすべて「陸路のみの最短経路」と「海路のみの最短経路」の組み合わせで表現できることがわかります。

• これらは陸路のみのグラフ、海路のみのグラフで全対間最短経路が求まっていれば良いので、ワーシャル・フロイド法でできます。

コストが前計算で求まることがわかったので、解は以下のようなDPで求まります。

DP[i][j] := Zの前からi要素までをすでに移動した(現在頂点がZ_i)、船の位置が頂点jという状態を達成するのにかかる最小コスト

上の陸路のみを使う時、海路を利用する時のコストの計算がそのままDPの遷移になります。

時間計算量はコストの前計算が 、DPの計算にです。TLE解より改善できていて、TLにも間に合います。

提出コード

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

template <class T, T INF>
vector<vector<T>> WF(int N, vector<tuple<int, int, T>> E, bool directed) {
    vector G(N, vector(N, INF));
    for (int i = 0 ; i < N ; i++) G[i][i] = 0;
    for (auto [u, v, c] : E) {
        G[u][v] = min(G[u][v], c);
        if (!directed) G[v][u] = min(G[v][u], c);
    }
    for (int k = 0 ; k < N ; k++) {
        for (int i = 0 ; i < N ; i++) {
            for (int j = 0 ; j < N ; j++) {
                G[i][j] = min(G[i][j], G[i][k] + G[k][j]);
            }
        }
    }
    return G;
}

bool solve() {
    int N, M; cin >> N >> M;

    if (N == 0) return false;

    vector<tuple<int, int, ll>> L, S;
    for (int _ = 0 ; _ < M ; _++) {
        int u, v, t; cin >> u >> v >> t;
        u--; v--;
        char c; cin >> c;
        if (c == 'L') {
            L.emplace_back(u, v, (ll)t);
        }
        else if (c == 'S') {
            S.emplace_back(u, v, (ll)t);
        }
        else {
            assert(!"input false");
        }
    }

    auto LT = WF<ll, (ll)1e18>(N, L, false), ST = WF<ll, (ll)1e16>(N, S, false);

    for (int i = 0 ; i < N ; i++) assert(ST[i][i] == 0LL);
    for (int i = 0 ; i < N ; i++) assert(LT[i][i] == 0LL);

    int R; cin >> R;
    vector<int> Z(R);
    for (auto& z : Z) cin >> z;
    for (auto& z : Z) z--;

    const ll INF = (ll)1e18;

    vector<ll> dp(N, INF); // pos of ship
    dp[Z[0]] = 0;

    for (int i = 0 ; i + 1 < R ; i++) {
        assert(count(dp.begin(), dp.end(), INF) < N);
        int u = Z[i], v = Z[i + 1];
        vector<ll> ndp(N, INF);
        for (int j = 0 ; j < N ; j++) {
            for (int k = 0 ; k < N ; k++) {
                ll cost = LT[u][j] + ST[j][k] + LT[k][v];
                ndp[k] = min(ndp[k], dp[j] + cost);
            }
        }
        for (int j = 0 ; j < N ; j++) {
            ll cost = LT[u][v];
            ndp[j] = min(ndp[j], dp[j] + cost);
        }
        dp = move(ndp);
    }
    cout << *min_element(dp.begin(), dp.end()) << endl;


    return true;
}

int main() {
    while (solve()) ;
}

• dp配列を使いまわしています
• 陸路のみを利用する遷移を忘れていてWAを出して、疑心難儀になってしまいassertを大量に仕込んでしまいました
• ICPC、JAGでありがちなwhile (solve()) ;

感想

• TLE解から更にグラフ改造パズルをしようとしていて、沼ってしまいました。
• 問題の状況について考えるのが大事だなと思わされました。
• 頂点数に対して辺数が多すぎるところからもワーシャルフロイドを使うことが察せそうです。