T3-13 Roadblocks G

思路解析

与上题的关键区别

本题允许重复经过节点和边（非简单路径），只要求路径总长度严格大于最短路径的最短路径。这使得解法完全不同——不需要枚举删边，而是用改进的 Dijkstra 同时维护最短和次短距离。

核心思路：双距离 Dijkstra

对每个节点同时维护两个值：

• d1[v]：从起点到 v 的最短距离
• d2[v]：从起点到 v 的严格次短距离

在 Dijkstra 松弛时，新距离 nd 有三种情况：

情况	操作
nd < d1[v]	原 d1 被挤到 d2，nd 成为新 d1
d1[v] < nd < d2[v]	nd 更新 d2
其他	不更新

最终 d2[N] 即为答案。

复杂度

• 时间：$O((N + R) \log N)$，一次改进 Dijkstra
• 空间：$O(N + R)$

---

逐行注释代码

#include <iostream>                        // 引入输入输出流
#include <vector>                          // 引入动态数组
#include <queue>                           // 引入优先队列
using namespace std;

typedef long long ll;                      // 使用 long long 防止溢出
typedef pair<ll, int> pli;                 // (距离, 节点) 二元组

const ll INF = 1e18;                       // 无穷大常量
const int MAXN = 5005;                     // 最大节点数

int n, r;                                  // n: 节点数, r: 边数
vector<pair<int, int>> adj[MAXN];          // 邻接表，adj[u] 存储 {v, w}
ll d1[MAXN], d2[MAXN];                     // d1: 最短距离, d2: 严格次短距离

void dijkstra() {
    // 小根堆，按距离从小到大排序
    priority_queue<pli, vector<pli>, greater<pli>> pq;

    for (int i = 1; i <= n; i++) {         // 初始化所有距离为无穷大
        d1[i] = INF;
        d2[i] = INF;
    }
    d1[1] = 0;                             // 起点最短距离为 0
    pq.push({0, 1});                       // 起点入队

    while (!pq.empty()) {
        auto [d, u] = pq.top();            // 取出距离最小的状态
        pq.pop();

        if (d > d2[u]) continue;           // 如果比次短距离还大，已过时，跳过

        for (auto [v, w] : adj[u]) {       // 遍历 u 的所有邻居
            ll nd = d + w;                 // 计算经过 u 到达 v 的新距离

            if (nd < d1[v]) {              // 情况1：新距离比最短还短
                swap(nd, d1[v]);           // 原 d1[v] 被挤出，暂存到 nd 中
                pq.push({d1[v], v});       // 新的最短距离入队
                // 注意：nd 现在是旧的 d1[v]，继续往下检查能否更新 d2
            }
            if (nd > d1[v] && nd < d2[v]) {// 情况2：严格介于 d1 和 d2 之间
                d2[v] = nd;                // 更新次短距离
                pq.push({d2[v], v});       // 次短距离入队
            }
            // 情况3：nd >= d2[v]，无法改善，不做任何操作
        }
    }
}

int main() {
    ios::sync_with_stdio(false);           // 关闭同步，加速 IO
    cin.tie(nullptr);                      // 解除 cin/cout 绑定

    cin >> n >> r;                          // 读入节点数和边数

    for (int i = 0; i < r; i++) {          // 读入 r 条边
        int a, b, d;
        cin >> a >> b >> d;
        adj[a].push_back({b, d});          // 无向图，存双向边
        adj[b].push_back({a, d});
    }

    dijkstra();                            // 运行双距离 Dijkstra

    cout << d2[n] << endl;                 // 输出节点 n 的严格次短距离

    return 0;
}