阅读量:0
题意
给定一张 n n n 点 m m m 边的无向图，请选择一条边，将其边权加倍，最多可使最短路增长多少？
思路
暴力做法：枚举所有边，将其边权加倍，跑一遍最短路，取最大值。
优化：由于修改最短路以外的边对最短路没有影响（除了变小），所以只需要枚举最短路上的边。
至于给边权加倍，我们不需要在邻接表中直接查找这条边来进行，只需在跑最短路时，传入两个参数 ( d u , d v ) (du,dv) (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; } 