AOJ 1182 Railway Connection
解法
めんどくさいダイクストラみたいな感じです。
ダイクストラするとき, d[v][c] = (直前に乗った電車が c であって今いる頂点が v であるようなものの最短距離) というのが一番わかりやすそうですが, r_jk が単調減少であることを利用すると, v -> (路線 c を通る) -> u -> (路線 c を通る) -> w と考えて (v -> u での値段) + (u -> w での値段) の値段とやるよりも, (v -> w での値段) のほうが必ず安いので, d[v] = (頂点 v までの最短距離) とするだけで良いです。
const int MAXN = 111; const int MAXC = 22; const int MAXP = 55; const int MAXD = 111*200; const int INF = 1e9; int d[MAXC][MAXN][MAXN]; ll value[MAXC][MAXD]; int p[MAXC], q[MAXC][MAXP], r[MAXC][MAXP]; int N, M, C, s, g; struct edge { int v; ll w; edge() {} edge(int v, ll w) : v(v), w(w) {}; }; vector<ll> dijkstra(int n, vector<vector<edge> >& G, int s) { vector<ll> d(n, LLONG_MAX/10); d[s] = 0; priority_queue<pair<ll, int> > que; que.push(make_pair(0ll, s)); while (!que.empty()) { auto p = que.top(); que.pop(); int u = p.second; ll dist = -p.first; if (dist > d[u]) continue; for (edge e : G[u]) { if (d[e.v] > d[u]+e.w) { d[e.v] = d[u] + e.w; que.push(make_pair(-d[e.v], e.v)); } } } return d; } int main() { cin.tie(0); ios::sync_with_stdio(false); while (cin >> N >> M >> C >> s >> g) { --s; --g; if (N==0) break; for (int c = 0; c < C; c++) { for (int i = 0; i < N; i++) { for (int j = 0; j < N; j++) d[c][i][j] = INF; d[c][i][i] = 0; } } for (int i = 0; i < M; i++) { int x, y, dist, c; cin >> x >> y >> dist >> c; --x; --y; --c; d[c][x][y] = d[c][y][x] = min(dist, d[c][x][y]); } for (int c = 0; c < C; c++) { for (int k = 0; k < N; k++) for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) { d[c][i][j] = min(d[c][i][j], d[c][i][k] + d[c][k][j]); } } for (int i = 0; i < C; i++) cin >> p[i]; for (int i = 0; i < C; i++) { for (int j = 1; j < p[i]; j++) cin >> q[i][j]; q[i][p[i]] = MAXD-1; for (int j = 1; j <= p[i]; j++) cin >> r[i][j]; for (int k = 1; k <= p[i]; k++) { for (int z = q[i][k-1]+1; z <= q[i][k]; z++) { value[i][z] = value[i][z-1] + r[i][k]; } } } vector<vector<edge> > G(N); for (int v = 0; v < N; v++) for (int u = 0; u < N; u++) { ll mini = INF; for (int c = 0; c < C; c++) { if (d[c][v][u] < MAXD) mini = min(mini, value[c][d[c][v][u]]); } if (mini < INF) { G[v].emplace_back(u, mini); G[u].emplace_back(v, mini); } } auto d = dijkstra(N, G, s); ll ans = d[g]; if (ans > INF) ans = -1; cout << ans << endl; } return 0; }