ICPC国内予選2009 D問題 : 離散的速度

問題. 離散的速度

単純無向グラフ $G = (V, E)$ とスタートとゴールの頂点 $s, g \in V$ が与えられる．また，辺 $e \in E$ には制限速度 $c(e)$ と距離 $d(e)$ が与えられている． $s$ から $g$ まで最小の時間で移動したい．ただし，各頂点では速度を1, 0, -1 だけ増加することができ，各移動する辺では制限速度を守りUターンすることができない．また，スタートからの移動後とゴール時の移動前の速度は1とする．

制約： $2 \le |V| \le 30$ ，　 $1 \le d \le 100$ ，　 $1 \le c \le 30$

解法. ダイクストラ法の変種

最短経路問題を解くダイクストラ法の変種である．ダイクストラ法ではスタートから移動した現在の頂点を状態として動的計画法を行うが，この問題では，直前の頂点，現在の頂点，速度と3つの状態を持つ必要がある．直前の頂点を状態として持つ理由はUターンが禁止されているからである．

計算時間： $c_{\max} = \max_{e \in E} c(e)$ 　とすると　 $O(|V|^2 c_{\max} \log |V|c_{\max})$ かな？

ソースコードを表示

#include <bits/stdc++.h>

using namespace std;

struct Edge {
    int v[2];
    double d, c;
    Edge() {}
    Edge(int v1, int v2, double d, double c) :
        v{v1, v2}, d(d), c(c) {}
};
bool operator<(const Edge &e1, const Edge &e2) {
    return e1.c >= e2.c;
}
using Edges = vector<Edge>;
using Graph = vector<Edges>;
const double INF = 1e8;

double MinimumTime(const int n, const int start, const int goal, const Graph &g) {
    // tm[前の頂点][現在の頂点][速度]
    vector<vector<vector<double>>> tm(n, vector<vector<double>>(n,
                                                                vector<double>(31, INF)));

    for (int v = 0; v < n; ++v) tm[v][start][1] = 0.0;

    // 前の頂点，現在の頂点，速度，経過時間
    priority_queue<Edge> que;
    for (const auto &e : g[start]) {
        que.push(Edge(start, e.v[1], 1, e.d));
        tm[start][e.v[1]][1] = e.d;
    }

    while (!que.empty()) {
        int prev = que.top().v[0], cur = que.top().v[1];
        double velocity = que.top().d, elapsed = que.top().c;
        que.pop();

        if (tm[prev][cur][velocity] < elapsed) continue;

        for (const auto &e : g[cur]) {
            if (e.v[1] == prev) continue;

            for (int add = -1; add <= 1; ++add) {
                const double nxt_velocity = velocity + add;

                if (nxt_velocity <= 0.0 || e.c < nxt_velocity) continue;

                double tmp_tm = elapsed + e.d / nxt_velocity;
                if (tmp_tm < tm[e.v[0]][e.v[1]][nxt_velocity]) {
                    tm[e.v[0]][e.v[1]][nxt_velocity] = tmp_tm;
                    que.push(Edge(cur, e.v[1], nxt_velocity, tmp_tm));
                }
            }
        }
    }

    double res = INF;
    for (int v = 0; v < n; ++v) res = min(res, tm[v][goal][1]);
    return (INF <= res) ? -1.0 : res;
}

int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << setprecision(8) << setiosflags(ios::fixed);

    int n, m, s, g, x, y, d, c;

    while (cin >> n >> m, n) {
        cin >> s >> g;

        Graph graph(n);
        for (int i = 0; i < m; ++i) {
            cin >> x >> y >> d >> c;
            graph[x - 1].emplace_back(Edge(x - 1, y - 1, d, c));
            graph[y - 1].emplace_back(Edge(y - 1, x - 1, d, c));
        }

        double time = MinimumTime(n, s - 1, g - 1, graph);
        if (time < 0.0) cout << "unreachable\n";
        else cout << time << '\n';
    }

    return 0;
}