首页 > 代码库 > LA 6891 Money Transfers（最短路）
LA 6891 Money Transfers（最短路）
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\n",ans);116 }117 return 0;118 }
LA 6891 Money Transfers（最短路）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。