AOJ2200 Mr. Rito Post Office
問題ページ
Mr. Rito Post Office | Aizu Online Judge
考えたこと
- 人がx、船がyにある状態を(x,y)と書くことにする
- ある頂点aにいるとき考えられる状態は (a,1)(a,2)(a,3)…(a,n) のN通り
- 頂点aから頂点bに移動するとき(a,1)→(b,1)(b,2)…(b,n)、(a,2)→(b,1)(b,2)…(b,n) … のN^2通りの移動方法がある
- (a,x) → (b,y) への移動にかかる最短距離がO(1)でわかればO(N^2R)で解ける
- 3*10^7くらいでそれっぽい計算量
- 前計算で最短距離を求められるようにしておきたい
- d[i][j] = ((i,j)に到達するまでの最短距離) として拡張dijkstraをするとできそう
- 計算量について考えると始点がO(N^2)でdijkstraがO(MlogN)あるので全体でO(N^2MlogN)
- これはTLEしそう
- 陸と海で別々に考えられないか?
- (a,x) → (b,y) へ移動するときに海を使うとする
- そのときは 陸でaから船があるxまで行く→海でyまで行く→陸でyからbまで行くと移動するのが最適
- x=yであれば海を使わないことも可能でそれならば陸でaからbまで行く
- 陸と海の道でそれぞれ最短経路を求めることができれば(a,x) → (b,y) の最短距離がわかる
- これはワーシャルフロイドを用いてO(N^3)で解ける
- したがって全体で O(N^3+N^2R) で解ける
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; #define int ll using VI = vector<int>; #define FOR(i, a, n) for (ll i = (ll)a; i < (ll)n; ++i) #define REP(i, n) FOR(i, 0, n) const int INF = (1LL<<30); template <typename T> T &chmin(T &a, const T &b) { return a = min(a, b); } template <typename T> T &chmax(T &a, const T &b) { return a = max(a, b); } int d1[205][205], d2[205][205]; signed main(void) { cin.tie(0); ios::sync_with_stdio(false); to_string(123); while(true) { int n, m; cin >> n >> m; if(!n) break; REP(i, n) REP(j, n) { d1[i][j] = i==j?0:INF; d2[i][j] = i==j?0:INF; } REP(i, m) { int x, y, c; char t; cin >> x >> y >> c >> t; x--, y--; if(t == 'L') { chmin(d1[x][y], c); chmin(d1[y][x], c); } else { chmin(d2[x][y], c); chmin(d2[y][x], c); } } REP(k, n) REP(i, n) REP(j, n) { chmin(d1[i][j], d1[i][k] + d1[k][j]); chmin(d2[i][j], d2[i][k] + d2[k][j]); } int r; cin >> r; VI cur(n, INF), nxt(n, INF); int now; cin >> now; now--; REP(i, n) cur[i] = i==now?0:INF; REP(i, r-1) { int g; cin >> g; g--; REP(j, n) { // (now, j) からスタートする REP(k, n) { // (g, k) を目的とする // 陸でnow->j 船でj->k 陸でk->g int tmp = d1[now][j] + d2[j][k] + d1[k][g]; // 陸だけで移動 if(j == k) chmin(tmp, d1[now][g]); chmin(nxt[k], cur[j] + tmp); } } cur = nxt; nxt.assign(n, INF); now = g; } int ret = INF; REP(i, n) chmin(ret, cur[i]); cout << ret << endl; } return 0; }