洛谷P2176 [USACO11DEC] RoadBlock S / [USACO14FEB]Roadblock G/S
创始人
2025-01-16 01:05:12
0次

题意

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

思路

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

// s - Source vertex. //  -> 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, greater> 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 #include using namespace std; #define int long long typedef pair 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> 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 dis(n, INF), pre(n, -1); 	vector vis(n, false); 	 	 	auto dij = [&](int s, int du = -1, int dv = -1){ 		priority_queue, greater> 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; } 

相关内容

热门资讯

推荐一款透视器!葫芦娃大厅透视... 推荐一款透视器!葫芦娃大厅透视器多功能AIapp,葫芦娃大厅果然是有透视器app1.葫芦娃大厅 选牌...
一分钟了解透视挂!东游大厅透视... 一分钟了解透视挂!东游大厅透视挂多功能AI脚本,东游大厅都是存在有透视挂脚本1、下载好东游大厅正确养...
我来向大家传授外挂!孔雀互娱外... 我来向大家传授外挂!孔雀互娱外挂多功能AI插件,孔雀互娱真是是真的有外挂插件1、完成孔雀互娱有辅助插...
我来教大家透视器!青岛大厅透视... 我来教大家透视器!青岛大厅透视器多功能AI插件,青岛大厅其实是有透视器插件1、青岛大厅免费辅助多个强...
一分钟带你了解辅助!067互娱... 一分钟带你了解辅助!067互娱辅助多功能AI教程,067互娱其实有辅助教程1、任何067互娱透视是真...
技术分享辅助!起点大厅辅助多功... 技术分享辅助!起点大厅辅助多功能AI技巧,起点大厅果然是有辅助技巧1、起透看视 起点大厅辅助软件价格...
一分钟教会你外挂!新玄龙外挂多... 一分钟教会你外挂!新玄龙外挂多功能AI插件,新玄龙真是是有外挂插件1、游戏颠覆性的策略玩法,独创攻略...
一分钟了解辅助!东游大厅辅助多... 一分钟了解辅助!东游大厅辅助多功能AI脚本,东游大厅总是有辅助脚本1、东游大厅透视辅助软件激活码多个...
我来教教你辅助!卡米大厅辅助多... 我来教教你辅助!卡米大厅辅助多功能AI方法,卡米大厅切实真的有辅助方法1、实时卡米大厅透视辅助更新:...
玩家必备教程辅助!辣椒大厅辅助... 玩家必备教程辅助!辣椒大厅辅助多功能AI软件,辣椒大厅原来真的有辅助软件1、许多玩家不知道辣椒大厅辅...