关键词:
https://vjudge.net/problem/UVALive-6891
题意:
给定一个加权无向图,还有起点和终点,现在有个SWERC公司,拥有图中的m个顶点,现在可以使图中的每一条边都加上k后求最短路,使得最短路上的点都包括在SWERC公司拥有的m个顶点中。求k的最大值。
思路:
对于k,采用二分法枚举。
我们可以求出起点到终点的最短路径,然后判断这些点是否都在SWERC公司当中即可。
还有容易错的一点!!
每个图中可能不止一条最短路,也许一条最短路时满足条件的,但是另外的是不满足的,那么这样也是不行的。
对于这个可以这样解决,在dijkstra算法当中,每次选择最短边加入时,在长度相同的情况下,我们优先选择不在SWERC公司中的顶点,这样这个问题就解决了。
1 #include<iostream> 2 #include<algorithm> 3 #include<cstring> 4 #include<cstdio> 5 #include<sstream> 6 #include<vector> 7 #include<stack> 8 #include<queue> 9 #include<cmath> 10 #include<map> 11 using namespace std; 12 typedef long long ll; 13 typedef pair<int,long long> pll; 14 const int INF=0x3f3f3f3f; 15 const int maxn=1000+5; 16 17 int n,p,src,dst,m; 18 19 int sw[maxn]; 20 ll d[maxn]; 21 int vis[maxn]; 22 int path[maxn]; 23 24 vector<pll> G[maxn]; 25 26 bool dijkstra(ll x) 27 { 28 memset(d,INF,sizeof(d)); 29 memset(vis,0,sizeof(vis)); 30 memset(path,0,sizeof(path)); 31 32 d[src]=0; 33 34 for(int i=1;i<=n;i++) 35 { 36 ll MIN =20000000000000LL; 37 int pos; 38 for(int j=1;j<=n;j++) 39 { 40 if(d[j]<=MIN && !vis[j]) 41 { 42 if(d[j]==MIN) {if(sw[j]==0) pos=j;} //这个很重要,优先考虑不在SW中的点 43 else 44 { 45 MIN=d[j]; 46 pos=j; 47 } 48 } 49 } 50 51 if(MIN==20000000000000LL) break; 52 if(pos==dst) break; 53 vis[pos]=1; 54 55 for(int j=0;j<G[pos].size();j++) 56 { 57 int v=G[pos][j].first; 58 if(vis[v]) continue; 59 ll w=G[pos][j].second+x; 60 if(d[pos]+w<d[v]) 61 { 62 d[v]=d[pos]+w; 63 path[v]=pos; 64 } 65 } 66 } 67 68 for(int i=dst;path[i]!=0;i=path[i]) 69 if(sw[i]==0) return false; 70 71 return true; 72 } 73 74 75 int main() 76 { 77 //freopen("input.txt","r",stdin); 78 while(~scanf("%d%d%d%d",&n,&p,&src,&dst)) 79 { 80 for(int i=1;i<=n;i++) G[i].clear(); 81 memset(sw,0,sizeof(sw)); 82 83 for(int i=0;i<p;i++) 84 { 85 int a,b; ll c; 86 scanf("%d%d%lld",&a,&b,&c); 87 G[a].push_back(make_pair(b,c)); 88 G[b].push_back(make_pair(a,c)); 89 } 90 91 scanf("%d",&m); 92 for(int i=0;i<m;i++) 93 { 94 int x; 95 scanf("%d",&x); 96 sw[x]=1; 97 } 98 99 ll ans=0; 100 ll L=0,R=20000000000000LL; 101 while(L<=R) 102 { 103 ll mid=(L+R)/2; 104 if(dijkstra(mid)) 105 { 106 ans=mid; 107 L=mid+1; 108 } 109 else R=mid-1; 110 } 111 112 113 if(ans==0) puts("Impossible"); 114 else if(ans==20000000000000LL) puts("Infinity"); 115 else printf("%lld ",ans); 116 } 117 return 0; 118 }
❤️数据结构入门❤️(3-5)-单源最短路
文章目录一、单源最短路的定义二、单源最短路的图解三、单源最短路的实现1、单源最短路的插入2、单源最短路的删除3、单源最短路的修改4、单源最短路的查找四、单源最短路的刷题实战一、单源最短路的定义二、单源最短... 查看详情
算法导论——单元最短路径(代码片段)
单源最短路径问题是指,给定一个图G=(V,E),希望找到从给定源结点s到每个节点v的最短路径。单源最短路径问题可以用来解决很多最短路径的变体。单目的地最短路径问题:找到从每个结点v到给定目的地结点t的最短路径。... 查看详情
训练指南uvalive-4080(最短路dijkstra+边修改+最短路树)(代码片段)
layout:posttitle:训练指南UVALive-4080(最短路Dijkstra+边修改+最短路树)author:"luowentaoaa"catalog:truemathjax:truetags:-Dijkstra-最短路树-图论-训练指南WarfareAndLogisticsUVALive-4080题意①先求任意两点间的最短路径累加和,其中不连通的边权... 查看详情
10.6最短路径问题(shortestpathproblem)
10.6最短路径问题(ShortestPathProblem)前言最短路径问题分两类:单源最短路径问题和多源最短路径问题单源最短路径diskstra算法:多源最短路径flody算法 查看详情
hdu5294tricksdevice(最大流+最短路)
...意:n个点,m条边。而且一个人从1走到n仅仅会走1到n的最短路径。问至少破坏几条边使原图的最短路不存在。最多破坏几条边使原图的最短路劲仍存在思路:1.跑一遍最短路。记录下全部最短路径,将这些最短路径的边以(0,1)... 查看详情
次短路
一、思想:求次短路,可以通过求最短路得到次短路长度1到n的次短路长度必然产生于:从1走到x的最短路+edge[x][y]+ y到n的最短路首先预处理好1到每一个节点的最短路,和n到每一个节点的最短路然后枚举每一条边作为中间边... 查看详情
图论最短路总结(代码片段)
写在前面:图论题的调试真感人让我们进入正题最短路是啥emmm顾名思义最短路就是求一个点到另外一个点的最小距离一般来说最短路分为:单源最短路和多源最短路单源最短路就是求一个源点到另外多个点的最短距离而多源最... 查看详情
最短路算法(代码片段)
目录最短路算法简述松弛操作Floyd算法算法原理实现方式代码实现传递闭包实际应用Dijkstra算法算法原理实现方式代码实现实际应用SPFA算法算法原理实现方式代码实现实际应用分层图最短路前置知识方法一方法二有点权的最短路... 查看详情
[最短路]aw3772.更新线路(bfs最短路模型+单源最短路的扩展应用+最短路计数+aw周赛008_3)(代码片段)
...析1.题目来源链接:3772.更新线路相似题:aw1134.最短路计数2.题目解析图论。有向边,边权为1,所以可以bfs求最短路,最短路算法也可以直接上,spfa在边权为1的情况下就是个bfs。需要求得每个点到终点的... 查看详情
最短路径
迪杰斯特拉(Dijkstra)算法是典型最短路径算法,用于计算一个节点到其他节点的最短路径。它的主要特点是以起始点为中心向外层层扩展(广度优先搜索思想),直到扩展到终点为止。算法思想:通过Dijkstra计算图G中的最短路径时,... 查看详情
最短路算法分析(代码片段)
最短路算法分析如下图所示,我们把边带有权值的图称为带权图。边的权值可以理解为两点之间的距离。一张图中任意两点间会有不同的路径相连。最短路就是指连接两点的这些路径中最短的一条。对于所有求最短路的算法,都... 查看详情
p1354房间最短路问题(建图&最短路)(代码片段)
P1354房间最短路问题(建图&最短路)建图跑最短路就行了,两点加边时特判下是否有墙挡住了。这里用floyd就可以过了//Problem:P1354房间最短路问题//Contest:Luogu//URL:https://www.luogu.com.cn/problem/P1354//MemoryLimit:125MB//TimeLimit:1000ms//Date:2... 查看详情
最短路问题
最短路问题总共可以用一张图来概括 查看详情
最短路问题
最短路问题总共可以用一张图来概括 查看详情
习题:最短路计数(spfa最短路计数)
最短路计数(洛谷1144)题目描述 给出一个N个顶点M条边的无向无 查看详情
最短路径之所有顶点间最短路径(图片格式)
最短路
Floyd算法求多源、无负权边的最短路。用矩阵记录图。时效性较差,时间复杂度O(V^3)。Floyd-Warshall算法(Floyd-Warshallalgorithm)是解决任意两点间的最短路径的一种算法,可以正确处理有向图或负权的最短路径问题。 查看详情
最短路和次短路问题,dijkstra算法
...目大意:3 *在一个有向图中,求从s到t两个点之间的最短路和比最短路长1的次短路的条数之和;4 *5 *算法思想:6 *用A*求第K短路,目测会超时,直接在dijkstra算法上求次短路;7 *将dist数组开成二维的,即dist[v][2],第二维... 查看详情