Aizu Online Judge 1182 - Railway Connection

問題

http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=1182

日本語版があるので省略。

解法

使う鉄道会社ごとに各駅間の最短距離をWarshall-Floyd法で求めます。すると求めた距離を使って各駅間の運賃を重みとするグラフを構築することができます。あとはDijkstra法で最小コストを求めるだけです。
他の人の実装を見ると、別にDijkstra法じゃなくても間に合うみたいですね。

ソースコード

#include <iostream>
#include <vector>
#include <cstring>
#include <utility>
#include <queue>
#include <algorithm>
using namespace std;

#define REP(i, x) for (int i = 0; i < (x); i++)
#define ALL(a) (a).begin(), (a).end()

typedef pair<int, int> P;

const int INF = 10000000;
const int MAX_C = 20;
const int MAX_N = 100;

struct edge {
    int to, cost;
};

int dist[MAX_C][MAX_N][MAX_N];  // ある鉄道会社のみを使ったときの距離
int cost[MAX_N];                // 最小コスト
int pi[MAX_C];                  // 鉄道会社ごとの区間の個数
vector<int> section[MAX_C];     // 区間幅
vector<int> fare[MAX_C];        // 運賃
vector<edge> graph[MAX_N];      // グラフ

int N, M, C, S, G;

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > Q;
    fill(cost, cost + N, INF);
    cost[s] = 0;
    Q.push(P(0, s));
    while (!Q.empty()) {
        P node = Q.top(); Q.pop();
        int v = node.second;
        if (cost[v] < node.first) continue;
        REP (i, graph[v].size()) {
            edge e = graph[v][i];
            if (cost[e.to] > cost[v] + e.cost) {
                cost[e.to] = cost[v] + e.cost;
                Q.push(P(cost[e.to], e.to));
            }
        }
    }
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);

    while (cin >> N >> M >> C >> S >> G, N | M | C | S | G) {
        // 初期化
        REP (i, N) {
            graph[i].clear();
        }

        REP (i, C) {
            section[i].clear();
            fare[i].clear();
        }

        REP (c, C) REP (i, N) REP (j, N) dist[c][i][j] = i == j ? 0 : INF;

        // 入力
        REP (i, M) {
            int x, y, d, c;
            cin >> x >> y >> d >> c;
            dist[c - 1][x - 1][y - 1] = dist[c - 1][y - 1][x - 1] = min(dist[c - 1][y - 1][x - 1], d);
        }

        REP (i, C) cin >> pi[i];

        REP (i, C) {
            section[i] = vector<int>(pi[i]);
            section[i][pi[i] - 1] = INF;    // 番兵
            REP (j, pi[i] - 1) {
                cin >> section[i][j];
            }

            fare[i] = vector<int>(pi[i]);
            REP (j, pi[i]) {
                cin >> fare[i][j];
            }
        }

        // Warshall-Floyd法
        REP (c, C) {
            REP (k, N) {
                REP (i, N) {
                    REP (j, N) {
                        dist[c][i][j] = min(dist[c][i][j],
                                            dist[c][i][k] + dist[c][k][j]);
                    }
                }
            }
        }

        // グラフを構築
        REP (i, N) {
            REP (j, N) {
                int temp_cost = -1;
                REP (c, C) {
                    if (dist[c][i][j] < INF) {
                        int temp_d = 0, temp_c = 0, sec_i = 0;
                        while (temp_d < dist[c][i][j]) {
                            temp_c += fare[c][sec_i] * (min(section[c][sec_i], dist[c][i][j]) - temp_d);
                            temp_d = section[c][sec_i];
                            sec_i++;
                        }
                        if (temp_cost == -1 || (temp_cost > temp_c)) {
                            temp_cost = temp_c;
                        }
                    }
                }
                if (temp_cost >= 0) {
                    graph[i].push_back((edge){j, temp_cost});
                }
            }
        }

        // Dijkstra法
        dijkstra(S - 1);

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

    return 0;
}

感想

難しかったですが解けてよかったです。あとは実装スピードですね。