洛谷P2176 [USACO11DEC] RoadBlock S / [USACO14FEB]Roadblock G/S

题意

给定一张 $n$ 点 $m$ 边的无向图，请选择一条边，将其边权加倍，最多可使最短路增长多少？

思路

暴力做法：枚举所有边，将其边权加倍，跑一遍最短路，取最大值。
优化：由于修改最短路以外的边对最短路没有影响（除了变小），所以只需要枚举最短路上的边。
至于给边权加倍，我们不需要在邻接表中直接查找这条边来进行，只需在跑最短路时，传入两个参数 $(du,dv)$ ，表示要加倍的边的两个端点，只要当前边相连的是这两个点，就把边权加倍。下面是这种方法的实现。

// s - Source vertex.
// <du, dv> -> Edge that needs to be doubled.
// The shortest distance is recorded in `dis`.
// The precursor of each point is recorded in `pre`.
auto dij = [&](int s, int du = -1, int dv = -1){priority_queue<PII, vector<PII>, greater<PII>> q;dis[s] = 0;q.push({0, s});while(q.size()){int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = true;for(auto &edge: G[u]){int v = edge.first, w = edge.second;// If the current edge needs to be doubledif((du == u && dv == v) || (du == v && dv == u)) w <<= 1;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({dis[v], v});// Record the precursor.if(du == -1 && dv == -1) pre[v] = u;}}}
};

代码

// Problem: P2176 [USACO11DEC] RoadBlock S / [USACO14FEB]Roadblock G/S
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P2176
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include<iostream>
#include<queue>
using namespace std;
#define int long long
typedef pair<int, int> PII;
const int INF = 0x3f3f3f3f;signed main() {ios::sync_with_stdio(0);cin.tie(0), cout.tie(0);int n, m;cin >> n >> m;vector<vector<PII>> G(n);for(int i = 0, u, v, w; i < m; i++){cin >> u >> v >> w;u--, v--;G[u].push_back({v, w});G[v].push_back({u, w});}vector<int> dis(n, INF), pre(n, -1);vector<bool> vis(n, false);auto dij = [&](int s, int du = -1, int dv = -1){priority_queue<PII, vector<PII>, greater<PII>> q;dis[s] = 0;q.push({0, s});while(q.size()){int u = q.top().second;q.pop();if(vis[u]) continue;vis[u] = true;for(auto &edge: G[u]){int v = edge.first, w = edge.second;if((du == u && dv == v) || (du == v && dv == u)) w <<= 1;if(dis[v] > dis[u] + w){dis[v] = dis[u] + w;q.push({dis[v], v});if(du == -1 && dv == -1) pre[v] = u;}}}};dij(0);int mind = dis.back(), ans = 0;for(int i = n - 1; pre[i] != -1; i = pre[i]){if(i == 0) continue;int u = pre[i], v = i;dis.assign(n, INF);vis.assign(n, false);dij(0, u, v);ans = max(ans, dis.back());}cout << ans - mind << endl;return 0;
}