AOJ 1182: 鉄道乗り継ぎ / Railway Connection
入力取るだけでも面倒でつらい。折れ線って何だ。
solution
Warshall-Floyd (とDijkstra)。 $O(cn^2 (n + \max d_i))$
- 会社を固定し、その会社の路線だけを使って全頂点対で距離を求める。Warshall-Floydをする
- 会社を固定し、その会社の路線だけを使って全頂点対で費用を求める。上の結果を用いる
- 全ての会社を使って、始点からの費用を求める。辺は$1$駅分のみを見るのでなくて、$1$路線を使って行けるところまで行くものとする
- Dijkstraでもよいが、Warshall-Floydで十分ぽい
implementation
#include <cstdio>
#include <queue>
#include <tuple>
#include <vector>
#define repeat(i, n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
template <class T> inline void setmax(T & a, T const & b) { a = max(a, b); }
template <class T> inline void setmin(T & a, T const & b) { a = min(a, b); }
template <typename X, typename T> auto vectors(X x, T a) { return vector<T>(x, a); }
template <typename X, typename Y, typename Z, typename... Zs> auto vectors(X x, Y y, Z z, Zs... zs) { auto cont = vectors(y, z, zs...); return vector<decltype(cont)>(x, cont); }
template <class T> using reversed_priority_queue = priority_queue<T, vector<T>, greater<T> >;
int main() {
constexpr int inf = 1e9+7;
while (true) {
// input
int n, m, company, start, goal; scanf("%d%d%d%d%d", &n, &m, &company, &start, &goal); -- start; -- goal;
if (n == 0) break;
auto g = vectors(company, n, vector<pair<int, int> >());
repeat (i, m) {
int x, y, d, c; scanf("%d%d%d%d", &x, &y, &d, &c); -- x; -- y; -- c;
g[c][x].emplace_back(y, d);
g[c][y].emplace_back(x, d);
}
vector<int> p(company);
repeat (c, company) {
scanf("%d", &p[c]);
}
vector<vector<int> > q(company);
vector<vector<int> > r(company);
repeat (c, company) {
q[c].resize(p[c] - 1);
repeat (i, p[c] - 1) {
scanf("%d", &q[c][i]);
}
r[c].resize(p[c]);
repeat (i, p[c]) {
scanf("%d", &r[c][i]);
}
}
// solve
// // initialize costs
auto dist = vectors(company, n, n, inf);
repeat (c, company) {
repeat (i, n) {
dist[c][i][i] = 0;
for (auto e : g[c][i]) {
int j, d; tie(j, d) = e;
setmin(dist[c][i][j], d);
}
}
repeat (k, n) repeat (i, n) repeat (j, n) { // Warshall-Floyd
setmin(dist[c][i][j], dist[c][i][k] + dist[c][k][j]);
}
}
auto cost = vectors(company, n, n, inf);
repeat (c, company) {
int max_dist = 0;
repeat (i, n) repeat (j, n) if (dist[c][i][j] != inf) {
setmax(max_dist, dist[c][i][j]);
}
vector<int> cost_at(max_dist + 3);
int i = 0;
repeat (d, cost_at.size() - 1) {
if (i < p[c] - 1 and d == q[c][i]) ++ i;
cost_at[d + 1] = cost_at[d] + r[c][i];
}
repeat (i, n) repeat (j, n) if (dist[c][i][j] != inf) {
cost[c][i][j] = cost_at[dist[c][i][j]];
}
}
// // Dijkstra
vector<int> result(n, inf);
vector<bool> fixed(n);
reversed_priority_queue<pair<int, int> > que;
result[start] = 0;
que.emplace(0, start);
while (not que.empty()) {
int i = que.top().second; que.pop();
if (fixed[i]) continue;
fixed[i] = true;
repeat (j, n) {
int d = inf;
repeat (c, company) {
setmin(d, result[i] + cost[c][i][j]);
}
if (d < result[j]) {
result[j] = d;
que.emplace(d, j);
}
}
}
// output
printf("%d\n", result[goal] == inf ? -1 : result[goal]);
}
return 0;
}