読者です 読者をやめる 読者になる 読者になる

mayoko’s diary

プロコンとかいろいろ。

AOJ 2200: Mr. Rito Post Office

AOJ
解法

普通に dp しようとすると dp[次目指す場所][今いる位置][船の位置] みたいになりそうですがこれだと状態数多すぎで間に合いません(というか dfs だとループになりそう)。

そこで, dp の遷移を限定することを考えます。z[i] -> z[i+1] に行くために使う手段としては,

  • 直接徒歩で行く
  • 船のいる場所まで徒歩で行ってから船で適当な点 v まで移動し, そこから z[i+1] まで徒歩

のどちらかしかありません。なので, あらかじめワーシャルフロイドで徒歩での最短距離, 船での最短距離を求めておき, dp[turn][ship] = (z[turn] までは到着し, 船が頂点 ship にある時の最短時間) を求めれば良いです。

遷移が限定できることに気付けば簡単。

const int MAXN = 222;
const int MAXR = 1111;
const ll INF = 1ll<<55;
int N, M, R;
// d1: land d2: sea
ll d1[MAXN][MAXN], d2[MAXN][MAXN];
int z[MAXR];

ll dp[MAXR][MAXN];

ll dfs(int turn, int ship) {
	ll& ret = dp[turn][ship];
	if (ret >= 0) return ret;
	if (turn == R-1) return ret = 0;
	// 徒歩
	ret = d1[z[turn]][z[turn+1]] + dfs(turn+1, ship);
	// 船
	for (int v = 0; v < N; v++) {
		ll tmp = d1[z[turn]][ship] + d2[ship][v] + d1[v][z[turn+1]];
		if (tmp >= INF) continue;
		tmp += dfs(turn+1, v);
		ret = min(ret, tmp);
	}
	return ret;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    while (cin >> N >> M) {
    	if (N==0 && M==0) break;
    	for (int i = 0; i < N; i++) {
    		for (int j = 0; j < N; j++) {
    			d1[i][j] = d2[i][j] = INF;
    		}
    		d1[i][i] = d2[i][i] = 0;
    	}
    	for (int i = 0; i < M; i++) {
    		int x, y, t;
    		char sl;
    		cin >> x >> y >> t >> sl;
    		x--; y--;
    		if (sl == 'L') {
    			d1[x][y] = min<ll>(d1[x][y], t);
    			d1[y][x] = d1[x][y];
    		} else {
    			d2[x][y] = min<ll>(d2[x][y], t);
    			d2[y][x] = d2[x][y];
    		}
    	}
    	for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) {
    		d1[i][j] = min(d1[i][j], d1[i][k] + d1[k][j]);
    		d2[i][j] = min(d2[i][j], d2[i][k] + d2[k][j]);
    	}
    	cin >> R;
    	for (int i = 0; i < R; i++) {
    		cin >> z[i];
    		z[i]--;
    	}
    	memset(dp, -1, sizeof(dp));
    	cout << dfs(0, z[0]) << endl;
    }
    return 0;
}