洛谷 P1119 灾后重建

// 第一版 ＝ 参照物：每个询问都在「已经修好的村庄」这张子图上，从头跑一次 Dijkstra
//
// 这是绝大多数人的第一反应，而且它**是对的** —— 问题只有一个：太慢。
//   每次 O(N²)，Q 次就是 50000 × 200² = **2 × 10⁹**。
// ⇒ 它同时也是这一页的对拍参照物：一行 Floyd 都没有，两条路完全独立。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int g[205][205], t[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) g[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int i, j, w;
        cin >> i >> j >> w;
        g[i][j] = min(g[i][j], w);
        g[j][i] = min(g[j][i], w);
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y, tt;
        cin >> x >> y >> tt;
        if (t[x] > tt || t[y] > tt) { cout << -1 << "\n"; continue; }
        vector<int> dist(n, INF);
        vector<char> done(n, 0);
        dist[x] = 0;
        for (int it = 0; it < n; it++) {
            int u = -1;
            for (int i = 0; i < n; i++)
                if (!done[i] && t[i] <= tt && dist[i] < INF && (u < 0 || dist[i] < dist[u])) u = i;
            if (u < 0) break;
            done[u] = 1;
            for (int v = 0; v < n; v++)
                if (t[v] <= tt && g[u][v] < INF && dist[u] + g[u][v] < dist[v])
                    dist[v] = dist[u] + g[u][v];
        }
        cout << (dist[y] >= INF ? -1 : dist[y]) << "\n";
    }
    return 0;
}

// 洛谷 P1119 灾后重建 —— ★ 这一版就能 AC
//
// ★★★ 关键的一步：Floyd 的 k 循环**本来就是「允许中转的点一个个加进去」**，
//     而这道题的村庄**正好也是一个个修好的** —— 两件事是同一件事。
//
// 题面白送了两句保证，缺一不可：
//   ① t[0] ≤ t[1] ≤ … ≤ t[N−1]      ⇒ 村庄修好的顺序就是编号顺序 ⇒ k 顺着 0..N−1 加
//   ② 询问的 t **不下降**            ⇒ 那个 k 指针**只往前走，从不回头**
// ⇒ 总复杂度 O(N³ + Q)，而不是每个询问一次 O(N³)。
//
// ⚠ 村庄编号是 **0 ~ N−1**。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;

int d[205][205], t[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int i, j, w;
        cin >> i >> j >> w;
        d[i][j] = min(d[i][j], w);
        d[j][i] = min(d[j][i], w);          // 公路是双向的
    }

    int q;
    cin >> q;
    int k = 0;                              // ★ 指针只往前走
    while (q--) {
        int x, y, tt;
        cin >> x >> y >> tt;
        while (k < n && t[k] <= tt) {       // ★ `<=`：第 t[k] 天当天即可通车
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            k++;
        }
        // ★ 两头自己都得修好了才谈得上路 —— 这一条和 d[x][y] 是两件事
        if (t[x] > tt || t[y] > tt || d[x][y] >= INF) cout << -1 << "\n";
        else cout << d[x][y] << "\n";
    }
    return 0;
}

// ✗ 错法①：只看 d[x][y]，忘了「x 或 y 自己还没修好」也要输出 −1
//
// 题面把这一条说了两遍（描述里一遍、输出格式里又一遍）：
//     「……或者村庄 x 或村庄 y 在第 t 天仍未重建完成，则需要输出 −1。」
//
// ⚠ 它和 d[x][y] 是**两件事**：x 和 y 之间可能早就有一条直达的公路（初始化时就填进表了），
//    可那两个村庄自己还是废墟。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int d[205][205], t[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int i, j, w;
        cin >> i >> j >> w;
        d[i][j] = min(d[i][j], w);
        d[j][i] = min(d[j][i], w);
    }
    int q;
    cin >> q;
    int k = 0;
    while (q--) {
        int x, y, tt;
        cin >> x >> y >> tt;
        while (k < n && t[k] <= tt) {
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            k++;
        }
        cout << (d[x][y] >= INF ? -1 : d[x][y]) << "\n";   // ✗ 少了 t[x] / t[y] 那两句
    }
    return 0;
}

// ✗ 错法②：把「第 t[k] 天修好」当成「第 t[k] 天还不能用」
//
// 题面：「……在第 tᵢ 天重建完成，**并且在当天即可通车**。」
// ⇒ 判据是 `t[k] <= tt`，写成 `<` 就整整晚了一天。
// ★ 这是一条**只有一天宽**的线：只有「询问的 t 正好等于某个村庄的 tᵢ」时它才现形。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int d[205][205], t[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int i, j, w;
        cin >> i >> j >> w;
        d[i][j] = min(d[i][j], w);
        d[j][i] = min(d[j][i], w);
    }
    int q;
    cin >> q;
    int k = 0;
    while (q--) {
        int x, y, tt;
        cin >> x >> y >> tt;
        while (k < n && t[k] < tt) {                      // ✗ 少了一个等号
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            k++;
        }
        if (t[x] >= tt || t[y] >= tt || d[x][y] >= INF) cout << -1 << "\n";   // ✗ 同一处 off-by-one
        else cout << d[x][y] << "\n";
    }
    return 0;
}

// ✗ 错法④：编号当成 1 ~ N —— 三重循环从 1 写起
//
// 这道题的村庄编号是 **0 ~ N−1**，而前面整整一张题单（[P1339] [P1629] [P1462] [B3647] [P3385]）
// 的编号都是 1 开头 —— 手感就是这么带过来的。
// ⇒ 0 号村庄**永远不会被当成中转站**，而一个根本不存在的 n 号村庄被塞进了循环。
//
// ★ 这是[第 27 章](/sol/p1352/)那条「同一张题单里编号基会翻面」的又一次现场。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int d[205][205], t[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) d[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int i, j, w;
        cin >> i >> j >> w;
        d[i][j] = min(d[i][j], w);
        d[j][i] = min(d[j][i], w);
    }
    int q;
    cin >> q;
    int k = 1;                                  // ✗ 从 1 号开始
    while (q--) {
        int x, y, tt;
        cin >> x >> y >> tt;
        while (k <= n && t[k] <= tt) {          // ✗ 一直数到 n（而 t[n] 根本没读进来）
            for (int i = 1; i <= n; i++)        // ✗ 0 号村庄永远当不上中转站
                for (int j = 1; j <= n; j++)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
            k++;
        }
        if (t[x] > tt || t[y] > tt || d[x][y] >= INF) cout << -1 << "\n";
        else cout << d[x][y] << "\n";
    }
    return 0;
}

// ？错法③：每个询问都把 k 指针从 0 重来 —— **答案永远是对的，就是跑不完**
//
// 忘了「询问的 t 不下降」这句保证的人，很自然会写成「每次重新把该修好的村庄加一遍」。
// 一次是 O(N³)，Q 次就是 50000 × 200³ = **4 × 10¹¹**。
//
// ★ 这一版是「[答案对但跑不完](/sol/p5019/)」那条线的又一个现场：
//   **官方样例挡不住它，对拍也挡不住它** —— 只能数次数。

#include <bits/stdc++.h>
using namespace std;
const int INF = 0x3f3f3f3f;
int d0[205][205], d[205][205], t[205];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    for (int i = 0; i < n; i++) cin >> t[i];
    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++) d0[i][j] = (i == j ? 0 : INF);
    for (int e = 0; e < m; e++) {
        int i, j, w;
        cin >> i >> j >> w;
        d0[i][j] = min(d0[i][j], w);
        d0[j][i] = min(d0[j][i], w);
    }
    int q;
    cin >> q;
    while (q--) {
        int x, y, tt;
        cin >> x >> y >> tt;
        memcpy(d, d0, sizeof(d0));                        // ？每次从原始的表重来
        for (int k = 0; k < n; k++) {
            if (t[k] > tt) break;
            for (int i = 0; i < n; i++)
                for (int j = 0; j < n; j++)
                    d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
        }
        if (t[x] > tt || t[y] > tt || d[x][y] >= INF) cout << -1 << "\n";
        else cout << d[x][y] << "\n";
    }
    return 0;
}