けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

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

問題文長い...

問題へのリンク

問題概要

 N 頂点、 M 辺の重み付き無向グラフが与えられる。各辺は「陸路」「海路」の属性がある。このグラフを、最初頂点  v_1 にいて、 v_1, v_2, \dots, v_R の順番に最短時間で巡りたい (順番的に後の頂点を先に通ってもよいが、その頂点より前の指定頂点をすべて巡った後でない限り、その頂点をクリアしたことにはならない)。

  • 海路は船を使用する
  • 船は最初、 v_1 に置いてある
  • 海路で頂点  v へと移動してそこから陸路を用いるときは頂点  v に船を置いて行くことになる
    • 再び海路を使用する場合には、頂点  v に戻って来る必要がある
  • 最後の船がどこにあるかは気にしなくてよい

制約

  •  2 \le N \le 200
  •  1 \le M \le 10000
  •  1 \le R \le 1000

考えたこと

グラフにチェックポイントがある系の問題。こういうのは、


前処理として、チェックポイント間の移動に要する最短時間を求めておく (Floyd-Warshall とか)


というのが定石ではある。今回は

  • dps[a][b] := 海路のみを使っての、a から b までの最短距離
  • dpl[a][b] := 陸路のみを使っての、a から b までの最短距離

として、これらを Floyd-Warshall とかで求めてみる。

その後は、海がどこにあるのかを管理しながらの DP をするのがよさそう。


dp[ i ][ j ] := 船を j に置いてある状態で、頂点 v_i にたどり着くまでの最小コスト


として DP する。DP 遷移は

  • 海を使わないとき、dp[i+1][j] = min(dp[i+1][j], dp[i][j] + dpl[v[i]][v[i+1]])
  • 途中で海を j から k まで使うとき、dp[i+1][k] = min(dp[i+1][k], dp[i][j] + dpl[v[i]][j] + dps[j][k] + dpl[k][v[i+1]])

計算量は  O(N^{3} + RN^{2})

#include <iostream>
#include <vector>
using namespace std;
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }
const long long INF = 1LL<<60;

int main() {
    int N, M;
    while (cin >> N >> M, N) {
        vector<vector<long long> > dps(N, vector<long long>(N, INF)), dpl(N, vector<long long>(N, INF));
        for (int v = 0; v < N; ++v) dps[v][v] = dpl[v][v] = 0;
        for (int e = 0; e < M; ++e) {
            int x, y;
            long long w;
            char type;
            cin >> x >> y >> w >> type;
            --x, --y;
            if (type == 'L') chmin(dpl[x][y], w), chmin(dpl[y][x], w);
            else chmin(dps[x][y], w), chmin(dps[y][x], w);
        }
        for (int k = 0; k < N; ++k) {
            for (int i = 0; i < N; ++i) {
                for (int j = 0; j < N; ++j) {
                    dpl[i][j] = min(dpl[i][j], dpl[i][k] + dpl[k][j]);
                    dps[i][j] = min(dps[i][j], dps[i][k] + dps[k][j]);
                }
            }
        }
        
        int R; cin >> R;
        vector<int> v(R);
        for (int i = 0; i < R; ++i) cin >> v[i], --v[i];
        
        vector<vector<long long> > dp(R, vector<long long>(N, INF));
        dp[0][v[0]] = 0;
        for (int i = 0; i < R-1; ++i) {
            for (int j = 0; j < N; ++j) {
                dp[i+1][j] = min(dp[i+1][j], dp[i][j] + dpl[v[i]][v[i+1]]);
                for (int k = 0; k < N; ++k) {
                    dp[i+1][k] = min(dp[i+1][k], dp[i][j] + dpl[v[i]][j] + dps[j][k] + dpl[k][v[i+1]]);
                }
            }
        }
        long long res = INF;
        for (int i = 0; i < N; ++i) {
            res = min(res, dp[R-1][i]);
        }
        cout << res << endl;
    }
}