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