AOJ2200 Mr. Rito Post Office - ferinの競プロ帳

問題ページ
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;
}