洛谷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 doubled
			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});
				// 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;
}