問題文長い...

問題概要

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

海路は船を使用する
船は最初、 $v_1$ に置いてある
海路で頂点へと移動してそこから陸路を用いるときは頂点に船を置いて行くことになる
- 再び海路を使用する場合には、頂点 $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;
    }
}