首页 > 代码库 > 洛谷 P1462 通往奥格瑞玛的道路（spfa+二分搜索）（4boy）
洛谷 P1462 通往奥格瑞玛的道路（spfa+二分搜索）（4boy）
原题:http://www.luogu.org/problem/show?pid=1462#sub
4boy:
大意:给出n个城市，有m条路，每经过一个城市都要交钱，每经过一条道路都要扣HP，有HP上限；要从1走到n，
求在HP没扣完的情况下，从1到n经过城市的最大花费的最小值。
思路:用二分搜索cost的值的最小值，用spfa搜索从1到n所需的最少HP，在spfa中判断cost[i]与x详见代码注释；
1 #include<iostream> 2 #include<cstring> 3 #include<queue> 4 #define maxn 100000 5 #define INF 0x3f3f3f3f 6 #define ll long long 7 using namespace std; 8 queue<int> q; 9 int n,m; 10 int edgenum=0,link[maxn],v[maxn]; 11 ll b,ans=-1,max_c=-1,cost[maxn],dis[maxn]; 12 struct EDGE //边表优化 13 { 14 int v,next; 15 ll val; 16 EDGE(){next=0;} 17 }edge[maxn]; 18 void add(int a,int b,int x) 19 { 20 edgenum++; 21 edge[edgenum].v=b; 22 edge[edgenum].val=x; 23 edge[edgenum].next=link[a]; 24 link[a]=edgenum; 25 } 26 void init() 27 { 28 cin>>n>>m>>b; 29 for(int i=1;i<=n;i++) 30 { 31 cin>>cost[i]; 32 max_c=max(max_c,cost[i]); 33 } 34 int x,y,l; 35 for(int i=1;i<=m;i++) 36 { 37 cin>>x>>y>>l; 38 add(x,y,l); 39 add(y,x,l); 40 } 41 } 42 bool spfa(ll x) 43 { 44 memset(dis,INF,sizeof(dis)); 45 memset(v,0,sizeof(v)); 46 dis[1]=0; 47 v[1]=1; 48 q.push(1); 49 while(!q.empty()) 50 { 51 int temp=q.front(); 52 q.pop(); 53 v[temp]=0; 54 for(int i=link[temp];i!=0;i=edge[i].next) 55 { 56 if(cost[edge[i].v]>x) continue; //此城市的cost>期望最小值x，则跳过 57 if(dis[edge[i].v]>dis[temp]+edge[i].val) 58 { 59 dis[edge[i].v]=dis[temp]+edge[i].val; 60 if(!v[edge[i].v]) 61 { 62 q.push(edge[i].v); 63 v[edge[i].v]=1; 64 } 65 } 66 } 67 } 68 if(dis[n]>b || dis[n]==(ll)INF) return false; //最短路的HP>上限 || 不通 则false 69 return true; 70 } 71 void work() 72 { 73 ll mid; 74 ll l=0,r=max_c; 75 while(l<=r) 76 { 77 mid=(r+l)>>1; 78 if(spfa(mid)==true) //已mid为值的cost可通，记录答案并搜索区间左移 79 { 80 r=mid-1; 81 ans=mid; 82 } 83 else //不通，搜索区间右移 84 { 85 l=mid+1; 86 } 87 } 88 if(ans==-1) cout<<"AFK"; 89 else cout<<ans; 90 } 91 void pt() 92 { 93 //if(spfa(10)) cout<<"fuck you"; 94 } 95 int main() 96 { 97 init(); 98 work(); 99 //pt();100 //system("pause");101 return 0;102 }
还有，请叫我子程序狂魔=-=
洛谷 P1462 通往奥格瑞玛的道路（spfa+二分搜索）（4boy）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。