AOJ1182 鉄道乗り継ぎ

問題ページ
鉄道乗り継ぎ | Aizu Online Judge

解法

各鉄道会社について駅i->駅jに移動するときに必要な距離をワーシャルフロイドを用いて求める。各鉄道会社についてある距離を移動するために必要なコストは求めることが可能なので駅i->駅jへ移動するのにかかる費用を求めることができる。あとは駅間を移動するコストを重みとしたグラフでsからgへの最短距離を求めればよく、これはワーシャルフロイドをすれば求められる。

ソースコード

#include <bits/stdc++.h>

using namespace std;
using ll = long long;
#define int ll
using VI = vector<int>;
using VVI = vector<VI>;

#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); }

int dist[25][105][105], cost[105][105];
signed main(void)
{
  cin.tie(0);
  ios::sync_with_stdio(false);

  while(true) {
    int n, m, com, s, g;
    cin >> n >> m >> com >> s >> g;
    if(!n) break;
    REP(i, 25) REP(j, 105) REP(k, 105) dist[i][j][k] = j==k?0:INF;
    VI x(m), y(m), d(m), c(m);
    REP(i, m) {
      cin >> x[i] >> y[i] >> d[i] >> c[i];
      x[i]--, y[i]--, c[i]--;
      chmin(dist[c[i]][x[i]][y[i]], d[i]);
      chmin(dist[c[i]][y[i]][x[i]], d[i]);
    }
    VI p(com);
    REP(i, com) cin >> p[i];
    VVI q(com), r(com);
    REP(i, com) {
      q[i] = VI(p[i]-1), r[i] = VI(p[i]);
      REP(j, p[i]-1) cin >> q[i][j];
      REP(j, p[i]) cin >> r[i][j];
    }

    // 会社lで移動するときの最短距離をWFで求める
    REP(l, com) REP(k, n) REP(i, n) REP(j, n) {
      chmin(dist[l][i][j], dist[l][i][k] + dist[l][k][j]);
    }

    REP(i, 105) REP(j, 105) cost[i][j] = i==j?0:INF;
    REP(l, com) {
      REP(i, n) REP(j, n) {
        // 会社lで距離dist[l][i][j]を移動するときにかかる運賃
        int tmp = 0;
        REP(k, p[l]-1) {
          if(dist[l][i][j] < q[l][k]) {
            tmp += (dist[l][i][j] - (k==0?0:q[l][k-1])) * r[l][k];
            break;
          } else {
            tmp += (q[l][k] - (k==0?0:q[l][k-1])) * r[l][k];
          }
        }
        if(p[l] == 1) {
          tmp = dist[l][i][j] * r[l][0];
        } else if(dist[l][i][j] > q[l].back()) {
          tmp += (dist[l][i][j] - q[l].back()) * r[l].back();
        }
        chmin(cost[i][j], tmp);
      }
    }

    REP(k, n) REP(i, n) REP(j, n) chmin(cost[i][j], cost[i][k] + cost[k][j]);

    if(cost[s-1][g-1] >= INF) cout << -1 << endl;
    else cout << cost[s-1][g-1] << endl;
  }

  return 0;
}