T3-4 RoadBlock S

题意理解

$N$ 个点 $M$ 条边的无向图，求从 $1$ 到 $N$ 的最短路。可以选择一条边使其长度加倍，问最大能使最短路增加多少。

---

思路分析

关键观察：

如果加倍的边不在原最短路上，那么最短路不会改变（原路径仍然可用）。

因此只需枚举最短路上的每条边，将其加倍后重新计算最短路。

算法流程：

1. 先跑一次 Dijkstra，求出原始最短路，并记录路径
2. 枚举最短路上的每条边 $(u, v, w)$，将其权值临时改为 $2w$
3. 重新跑 Dijkstra，计算新的最短路
4. 增量 = 新最短路 - 原最短路，取所有增量的最大值

复杂度分析：

最短路上最多 $N-1$ 条边，每次 Dijkstra 为 $O((N+M) log N)$，总复杂度 $O(N \cdot (N+M) \cdot log N)$，可以通过。

---

参考代码

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 105;       // 最大点数
const int MAXM = 5005;      // 最大边数
const long long INF = 1e18; // 无穷大

int n, m;                   // 点数、边数
int head[MAXN], cnt;        // 邻接表头指针、边计数器

struct Edge {               // 边结构体
    int to, nxt;            // 终点、下一条边
    long long w;            // 边权
} e[MAXM * 2];              // 双向边所以开两倍

void addEdge(int u, int v, long long w) {  // 添加一条从u到v权值为w的边
    e[++cnt] = {v, head[u], w};            // 新边指向原来的第一条边
    head[u] = cnt;                          // 更新头指针
}

long long dis[MAXN];        // dis[i]表示起点到i的最短距离
int pre[MAXN];              // pre[i]表示最短路上到达i的边编号
bool vis[MAXN];             // vis[i]表示i是否已确定最短路

long long dijkstra(int ban) {              // ban为要加倍的边编号，-1表示不加倍
    memset(dis, 0x3f, sizeof(dis));        // 初始化距离为无穷大
    memset(vis, false, sizeof(vis));       // 初始化所有点未访问
    priority_queue<pair<long long, int>, vector<pair<long long, int>>, greater<pair<long long, int>>> pq;  // 小根堆
    
    dis[1] = 0;                            // 起点距离为0
    pq.push({0, 1});                       // 起点入队
    
    while (!pq.empty()) {                  // 队列非空时循环
        int u = pq.top().second;           // 取出当前距离最小的点
        pq.pop();                          // 弹出堆顶
        
        if (vis[u]) continue;              // 如果已处理过则跳过
        vis[u] = true;                     // 标记为已处理
        
        for (int i = head[u]; i; i = e[i].nxt) {  // 遍历u的所有出边
            int v = e[i].to;               // 边的终点
            long long w = e[i].w;          // 边的权值
            if (i == ban || i == (ban ^ 1)) {     // 如果是要加倍的边
                w *= 2;                    // 权值翻倍（异或1处理反向边）
            }
            
            if (dis[u] + w < dis[v]) {     // 如果能更新最短路
                dis[v] = dis[u] + w;       // 更新距离
                if (ban == -1) {           // 只在第一次dijkstra时记录路径
                    pre[v] = i;            // 记录到达v的边编号
                }
                pq.push({dis[v], v});      // 将v入队
            }
        }
    }
    return dis[n];                         // 返回到终点n的最短距离
}

int main() {
    cin >> n >> m;                         // 读入点数和边数
    cnt = 1;                               // 边从2开始编号，方便用异或处理反向边
    
    for (int i = 0; i < m; i++) {          // 读入m条边
        int a, b;                          // 边的两个端点
        long long l;                       // 边的长度
        cin >> a >> b >> l;                // 读入边的信息
        addEdge(a, b, l);                  // 添加a到b的边
        addEdge(b, a, l);                  // 添加b到a的边（无向图）
    }
    
    long long origin = dijkstra(-1);       // 计算原始最短路（不加倍任何边）
    
    vector<int> path;                      // 存储最短路上的边编号
    for (int v = n; v != 1; v = e[pre[v] ^ 1].to) {  // 从终点回溯到起点
        path.push_back(pre[v]);            // 记录这条边的编号
    }
    
    long long ans = 0;                     // 答案：最大增量
    for (int edgeId : path) {              // 枚举最短路上的每条边
        long long newDis = dijkstra(edgeId);       // 加倍该边后重新计算最短路
        ans = max(ans, newDis - origin);   // 更新最大增量
    }
    
    cout << ans << endl;                   // 输出答案
    return 0;
}