AOJ 2200: Mr. Rito Post Office
解法
普通に 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; }