洛谷 P2865 [USACO06NOV] Roadblocks G

// 第一版：把「第二短路径」当成「第二短的**简单路径**」，DFS 枚举
//
// 这是很自然的第一反应 —— 而题面第三段明写着：
//     「第二短路径可以与任何最短路径共享道路，**并且可以回溯，即多次使用相同的道路或交叉路口**。」
//
// ⚠ 最小反例只要**一条边**：`2 1 / 1 2 100`
//    最短路是 100，而次短路是 `1 → 2 → 1 → 2` = **300**（走回去再走回来）。
//    枚举简单路径的话，从 1 到 2 只有一条 ⇒ 它根本找不到第二条。
// ⚠ 这一版只能跑很小的图（枚举简单路径是指数的），它是用来看清那句题面的，不是拿去交的。

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

int n, r;
vector<vector<pair<int, int>>> g;
vector<char> vis;
set<int> lens;

void dfs(int u, int cur) {
    if (cur > 200000) return;
    if (u == n) { lens.insert(cur); return; }
    for (auto [v, w] : g[u])
        if (!vis[v]) { vis[v] = 1; dfs(v, cur + w); vis[v] = 0; }
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> r;
    g.assign(n + 1, {});
    for (int e = 0; e < r; e++) {
        int a, b, d;
        cin >> a >> b >> d;
        g[a].push_back({b, d});
        g[b].push_back({a, d});
    }
    vis.assign(n + 1, 0);
    vis[1] = 1;
    dfs(1, 0);
    if ((int)lens.size() < 2) { cout << INF << "\n"; return 0; }   // ✗ 找不到第二条
    auto it = lens.begin();
    ++it;
    cout << *it << "\n";
    return 0;
}

// 洛谷 P2865 [USACO06NOV] Roadblocks G —— ★ 这一版就能 AC
//
// ★ 关键的一步：**状态不再只是「在哪个点」，而是「在哪个点 ＋ 这是到它的第几短」**。
//    每个点维护两个距离 d1（最短）和 d2（严格次短），松弛时三选一：
//      · 比 d1 还短 ⇒ 旧的 d1 被**挤下来**变成 d2，新值当 d1；
//      · 严格夹在 d1 和 d2 之间 ⇒ 换掉 d2；
//      · 其余 ⇒ 丢掉。
//
// ⚠ 「严格」这两个字是题面自己写的：「第二短路径是长度**比最短路径长**的最短路径」。
// ⚠ 而次短路**允许重复经过边和点** —— 所以它不一定是一条简单路径（第 ① 步那个反例）。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r;
    cin >> n >> r;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int e = 0; e < r; e++) {
        int a, b, d;
        cin >> a >> b >> d;
        g[a].push_back({b, d});
        g[b].push_back({a, d});             // 双向道路
    }

    vector<int> d1(n + 1, INF), d2(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    d1[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > d2[u]) continue;            // ★ 过期的：连次短都不如
        for (auto [v, w] : g[u]) {
            int nd = d + w;
            if (nd < d1[v]) {
                d2[v] = d1[v];              // ★ 旧的最短被挤成次短
                d1[v] = nd;
                q.push({d1[v], v});
                if (d2[v] < INF) q.push({d2[v], v});
            } else if (nd > d1[v] && nd < d2[v]) {   // ★ 严格大于 d1
                d2[v] = nd;
                q.push({d2[v], v});
            }
        }
    }
    cout << d2[n] << "\n";
    return 0;
}

// ✗ 错法①：把「严格次短」写成「非严格次短」
//
// 题面：「第二短路径是长度**比最短路径长**的最短路径
//        （即，如果存在两条或多条最短路径，第二短路径是长度比这些路径长但不比任何其他路径长的路径）」
// ⇒ 括号里那半句是专门为这个坑写的：**并列的最短路不算第二短。**
//
// 这一版把 `nd > d1[v]` 写成 `nd >= d1[v]`，于是只要存在两条一样长的最短路，
// 它就会把「另一条最短路」当成次短路交上去。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r;
    cin >> n >> r;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int e = 0; e < r; e++) {
        int a, b, d;
        cin >> a >> b >> d;
        g[a].push_back({b, d});
        g[b].push_back({a, d});
    }
    vector<int> d1(n + 1, INF), d2(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    d1[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > d2[u]) continue;
        for (auto [v, w] : g[u]) {
            int nd = d + w;
            if (nd < d1[v]) {
                d2[v] = d1[v]; d1[v] = nd;
                q.push({d1[v], v});
                if (d2[v] < INF) q.push({d2[v], v});
            } else if (nd >= d1[v] && nd < d2[v]) {   // ✗ 少了一个「严格」
                d2[v] = nd;
                q.push({d2[v], v});
            }
        }
    }
    cout << d2[n] << "\n";
    return 0;
}

// ✗ 错法②：d1 被刷新时，忘了把旧的 d1「挤下来」当 d2
//
// 这一处最容易漏：新来的 nd 比 d1 还短，那**原来那个 d1 就是一条合法的、更长的路** ——
// 它应该顺位变成 d2。少了这一行，很多次短路会被直接丢掉。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r;
    cin >> n >> r;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int e = 0; e < r; e++) {
        int a, b, d;
        cin >> a >> b >> d;
        g[a].push_back({b, d});
        g[b].push_back({a, d});
    }
    vector<int> d1(n + 1, INF), d2(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    d1[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > d2[u]) continue;
        for (auto [v, w] : g[u]) {
            int nd = d + w;
            if (nd < d1[v]) {
                d1[v] = nd;                          // ✗ 旧的 d1 就这么丢了
                q.push({d1[v], v});
            } else if (nd > d1[v] && nd < d2[v]) {
                d2[v] = nd;
                q.push({d2[v], v});
            }
        }
    }
    cout << d2[n] << "\n";
    return 0;
}

// ✗ 错法③：双向道路只存一遍
//
// 题面：「每条道路连接 N 个交叉路口中的两个」，输入格式那节写的是「描述连接交叉路口 A 和 B 的一条道路」——
// 而这道题的次短路**要靠往回走**才走得出来（第 ① 步那个一条边的反例），
// ⇒ 少了反向边，连「回溯」这件事都做不到。

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

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r;
    cin >> n >> r;
    vector<vector<pair<int, int>>> g(n + 1);
    for (int e = 0; e < r; e++) {
        int a, b, d;
        cin >> a >> b >> d;
        g[a].push_back({b, d});                      // ✗ 少了反着那一行
    }
    vector<int> d1(n + 1, INF), d2(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    d1[1] = 0;
    q.push({0, 1});
    while (!q.empty()) {
        auto [d, u] = q.top();
        q.pop();
        if (d > d2[u]) continue;
        for (auto [v, w] : g[u]) {
            int nd = d + w;
            if (nd < d1[v]) {
                d2[v] = d1[v]; d1[v] = nd;
                q.push({d1[v], v});
                if (d2[v] < INF) q.push({d2[v], v});
            } else if (nd > d1[v] && nd < d2[v]) {
                d2[v] = nd;
                q.push({d2[v], v});
            }
        }
    }
    cout << d2[n] << "\n";
    return 0;
}

// ★ 另一条路：两次 Dijkstra ＋ 枚举每条边
//
// 从 1 号点跑一次得到 ds[]，从 N 号点跑一次得到 dt[]（图是无向的，直接反着跑就行）。
// 那么「经过边 (u, v)」的最短走法就是 ds[u] + w + dt[v]；
// 在所有这样的值里挑**严格大于最短路**的最小值，就是次短路。
//
// ★ 它和 d1/d2 那份一行代码都不共享 —— 对拍时两条独立的路。

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

static vector<int> dij(int n, vector<vector<pair<int, int>>>& g, int s) {
    vector<int> d(n + 1, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> q;
    d[s] = 0;
    q.push({0, s});
    while (!q.empty()) {
        auto [dd, u] = q.top();
        q.pop();
        if (dd > d[u]) continue;
        for (auto [v, w] : g[u])
            if (dd + w < d[v]) { d[v] = dd + w; q.push({d[v], v}); }
    }
    return d;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, r;
    cin >> n >> r;
    vector<vector<pair<int, int>>> g(n + 1);
    vector<array<int, 3>> es;
    for (int e = 0; e < r; e++) {
        int a, b, d;
        cin >> a >> b >> d;
        g[a].push_back({b, d});
        g[b].push_back({a, d});
        es.push_back({a, b, d});
    }
    auto ds = dij(n, g, 1), dt = dij(n, g, n);
    int best = ds[n], sec = INF;
    for (auto& e : es)
        for (int dir = 0; dir < 2; dir++) {
            int u = dir ? e[1] : e[0], v = dir ? e[0] : e[1];
            if (ds[u] >= INF || dt[v] >= INF) continue;
            int cand = ds[u] + e[2] + dt[v];
            if (cand > best && cand < sec) sec = cand;      // ★ 严格大于
        }
    cout << sec << "\n";
    return 0;
}