洛谷 P1266 [BalticOI 2002] 速度限制

// ✗ 错法④：回溯完忘了把路径翻过来
//
// 和算法一点关系都没有 —— 但它是这道题**唯一一个官方样例挡得住**的错法
// （样例答案 `0 5 2 3 1` 倒过来是 `1 3 2 5 0`，一眼就不对）。

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 501;
const double INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, D;
    cin >> n >> m >> D;
    vector<vector<array<int, 3>>> g(n);
    for (int e = 0; e < m; e++) {
        int a, b, v, l;
        cin >> a >> b >> v >> l;
        g[a].push_back({b, v, l});
    }
    vector<vector<double>> dist(n, vector<double>(MAXV, INF));
    vector<vector<pair<int, int>>> from(n, vector<pair<int, int>>(MAXV, {-1, -1}));
    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<>> q;
    dist[0][70] = 0;
    q.push({0.0, 0, 70});
    while (!q.empty()) {
        auto [d, u, s] = q.top();
        q.pop();
        if (d > dist[u][s] + 1e-12) continue;
        for (auto [v, lim, len] : g[u]) {
            int ns = lim ? lim : s;
            double nd = d + (double)len / ns;
            if (nd < dist[v][ns] - 1e-12) {
                dist[v][ns] = nd;
                from[v][ns] = {u, s};
                q.push({nd, v, ns});
            }
        }
    }
    int best = -1;
    for (int s = 1; s < MAXV; s++)
        if (dist[D][s] < INF && (best < 0 || dist[D][s] < dist[D][best])) best = s;
    vector<int> path;
    for (int u = D, s = best; u >= 0; ) {
        path.push_back(u);
        auto [pu, ps] = from[u][s];
        u = pu; s = ps;
    }
    // ✗ 少了 reverse
    for (size_t i = 0; i < path.size(); i++) cout << path[i] << " \n"[i + 1 == path.size()];
    return 0;
}

// 洛谷 P1266 [BalticOI 2002] 速度限制 —— ★ 这一版就能 AC
//
// ★★★ 关键的一步：**状态不是「在哪个路口」，是「在哪个路口 ＋ 现在开多快」**。
//     因为一条 V = 0 的路「按原来的速度行驶」—— 走它花多久，取决于你**是怎么来的**。
//
// 速度的取值有限：题面 0 ≤ V ≤ 500，而 V = 0 表示「不改速度」
// ⇒ 真正可能的速度只有「初速 70」和输入里出现过的那些 V，一律落在 1..500 里。
// ⇒ 状态数 150 × 501 = 75150，边数 22500 × 501 —— 分层图 Dijkstra 随便跑。
//
// ⚠ 要输出的是**路径**，不是时间 ⇒ 每个状态记一个前驱，最后倒着回溯再翻过来。
// ⚠ 路口编号是 **0 ~ N−1**，起点是 0 号。

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 501;                        // 速度 1..500
const double INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, D;
    cin >> n >> m >> D;
    vector<vector<array<int, 3>>> g(n);      // {到哪儿, 限速 V, 长度 L}
    for (int e = 0; e < m; e++) {
        int a, b, v, l;
        cin >> a >> b >> v >> l;
        g[a].push_back({b, v, l});
    }

    vector<vector<double>> dist(n, vector<double>(MAXV, INF));
    vector<vector<pair<int, int>>> from(n, vector<pair<int, int>>(MAXV, {-1, -1}));
    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<>> q;
    dist[0][70] = 0;                         // ★ 起点 0 号，初速 70
    q.push({0.0, 0, 70});
    while (!q.empty()) {
        auto [d, u, s] = q.top();
        q.pop();
        if (d > dist[u][s] + 1e-12) continue;
        for (auto [v, lim, len] : g[u]) {
            int ns = lim ? lim : s;          // ★ V = 0 就沿用当前速度
            double nd = d + (double)len / ns;
            if (nd < dist[v][ns] - 1e-12) {
                dist[v][ns] = nd;
                from[v][ns] = {u, s};
                q.push({nd, v, ns});
            }
        }
    }

    int best = -1;
    for (int s = 1; s < MAXV; s++)
        if (dist[D][s] < INF && (best < 0 || dist[D][s] < dist[D][best])) best = s;

    vector<int> path;
    for (int u = D, s = best; u >= 0; ) {
        path.push_back(u);
        auto [pu, ps] = from[u][s];
        u = pu;
        s = ps;
    }
    reverse(path.begin(), path.end());       // ★ 回溯是倒着的，要翻过来
    for (size_t i = 0; i < path.size(); i++) cout << path[i] << " \n"[i + 1 == path.size()];
    return 0;
}

// ✗ 错法①：状态里只有「在哪个路口」，把速度记成每个点一个值
//
// 这是最自然的第一反应：跑普通 Dijkstra，顺手拿一个 spd[] 记「到达这个点时的速度」。
// ⚠ 它错在**同一个路口可以用不同的速度到达**，而哪一个更划算，
//    取决于后面那段路里有没有 V = 0 的边 —— 「先到」不等于「更好」。
// ⇒ 这就是本章那句「Dijkstra 的贪心要成立，得先把状态定对」的现场
//   （[第 32 章 P1073](/sol/p1073/) 那条的同款）。

#include <bits/stdc++.h>
using namespace std;
const double INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, D;
    cin >> n >> m >> D;
    vector<vector<array<int, 3>>> g(n);
    for (int e = 0; e < m; e++) {
        int a, b, v, l;
        cin >> a >> b >> v >> l;
        g[a].push_back({b, v, l});
    }
    vector<double> dist(n, INF);
    vector<int> spd(n, 0), from(n, -1);
    priority_queue<pair<double, int>, vector<pair<double, int>>, greater<>> q;
    dist[0] = 0;
    spd[0] = 70;
    q.push({0.0, 0});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > dist[u] + 1e-12) continue;
        for (auto [v, lim, len] : g[u]) {
            int ns = lim ? lim : spd[u];             // ✗ 只有一个 spd[u] 可用
            double nd = d + (double)len / ns;
            if (nd < dist[v] - 1e-12) {
                dist[v] = nd;
                spd[v] = ns;
                from[v] = u;
                q.push({nd, v});
            }
        }
    }
    vector<int> path;
    for (int u = D; u >= 0; u = from[u]) path.push_back(u);
    reverse(path.begin(), path.end());
    for (size_t i = 0; i < path.size(); i++) cout << path[i] << " \n"[i + 1 == path.size()];
    return 0;
}

// ✗ 错法②：把 V = 0 读成「这条路不限速」
//
// 题面写的是：「如果 V 是 0，表示这条路的**限速未知**」，而且下一段补了做法 ——
//     「否则 T = L / V_old，V_old 是你到达该路口前的速度。」
// 「未知」不是「不限」。读成不限速的话，这条边的耗时会被算成 0（想开多快开多快），
// 于是它会一头扎进所有 V = 0 的路。

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 501;
const double INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, D;
    cin >> n >> m >> D;
    vector<vector<array<int, 3>>> g(n);
    for (int e = 0; e < m; e++) {
        int a, b, v, l;
        cin >> a >> b >> v >> l;
        g[a].push_back({b, v, l});
    }
    vector<vector<double>> dist(n, vector<double>(MAXV, INF));
    vector<vector<pair<int, int>>> from(n, vector<pair<int, int>>(MAXV, {-1, -1}));
    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<>> q;
    dist[0][70] = 0;
    q.push({0.0, 0, 70});
    while (!q.empty()) {
        auto [d, u, s] = q.top();
        q.pop();
        if (d > dist[u][s] + 1e-12) continue;
        for (auto [v, lim, len] : g[u]) {
            int ns = lim ? lim : s;
            double nd = d + (lim ? (double)len / lim : 0.0);   // ✗ V = 0 当成不花时间
            if (nd < dist[v][ns] - 1e-12) {
                dist[v][ns] = nd;
                from[v][ns] = {u, s};
                q.push({nd, v, ns});
            }
        }
    }
    int best = -1;
    for (int s = 1; s < MAXV; s++)
        if (dist[D][s] < INF && (best < 0 || dist[D][s] < dist[D][best])) best = s;
    vector<int> path;
    for (int u = D, s = best; u >= 0; ) {
        path.push_back(u);
        auto [pu, ps] = from[u][s];
        u = pu; s = ps;
    }
    reverse(path.begin(), path.end());
    for (size_t i = 0; i < path.size(); i++) cout << path[i] << " \n"[i + 1 == path.size()];
    return 0;
}

// ✗ 错法③：忘了那句「开始时你位于 0 点，并且**速度为 70**」
//
// 那句话藏在输入格式那一节的最后一行 —— 很容易读过去。
// 这一版把初速当成「随便一个大数」（500，也就是题面允许的最大限速），
// 于是从 0 号出发的 V = 0 那些路会被算得比实际快。

#include <bits/stdc++.h>
using namespace std;
const int MAXV = 501;
const double INF = 1e18;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m, D;
    cin >> n >> m >> D;
    vector<vector<array<int, 3>>> g(n);
    for (int e = 0; e < m; e++) {
        int a, b, v, l;
        cin >> a >> b >> v >> l;
        g[a].push_back({b, v, l});
    }
    vector<vector<double>> dist(n, vector<double>(MAXV, INF));
    vector<vector<pair<int, int>>> from(n, vector<pair<int, int>>(MAXV, {-1, -1}));
    priority_queue<tuple<double, int, int>, vector<tuple<double, int, int>>, greater<>> q;
    dist[0][500] = 0;                                  // ✗ 初速写成 500
    q.push({0.0, 0, 500});
    while (!q.empty()) {
        auto [d, u, s] = q.top();
        q.pop();
        if (d > dist[u][s] + 1e-12) continue;
        for (auto [v, lim, len] : g[u]) {
            int ns = lim ? lim : s;
            double nd = d + (double)len / ns;
            if (nd < dist[v][ns] - 1e-12) {
                dist[v][ns] = nd;
                from[v][ns] = {u, s};
                q.push({nd, v, ns});
            }
        }
    }
    int best = -1;
    for (int s = 1; s < MAXV; s++)
        if (dist[D][s] < INF && (best < 0 || dist[D][s] < dist[D][best])) best = s;
    vector<int> path;
    for (int u = D, s = best; u >= 0; ) {
        path.push_back(u);
        auto [pu, ps] = from[u][s];
        u = pu; s = ps;
    }
    reverse(path.begin(), path.end());
    for (size_t i = 0; i < path.size(); i++) cout << path[i] << " \n"[i + 1 == path.size()];
    return 0;
}