P1462 通往奥格瑞玛的道路

标签：瑞玛 val int 血量 P1462 奥格 dis

城市之间有 mm 条双向的公路，连接着两个城市，从某个城市到另一个城市，会遭到联盟的攻击，进而损失一定的血量。

每次经过一个城市，都会被收取一定的过路费（包括起点和终点）。路上并没有收费站。

假设 1 为暴风城，n为奥格瑞玛，而他的血量最多为 b，出发时他的血量是满的。如果他的血量降低至负数，则他就无法到达奥格瑞玛。

不希望花很多钱，他想知道，在可以到达奥格瑞玛的情况下，他所经过的所有城市中最多的一次收取的费用的最小值是多少。

 

二分这个最多的费用 mid，检验时跑最短路，看能否不死( 路径上的最大值为mid)

#include <bits/stdc++.h>
using namespace std ;
 const int N=1e4+3,M=2e5;
 
 int n,m,dis[N],vis[N];
 int K,val[N],w[M],nxt[M],go[M],hd[N],all;
 
 void add(int x,int y,int z){
 	 go[++all]=y; w[all]=z,nxt[all]=hd[x],hd[x]=all;
 }
 
 int chk(int md){
 	int i,x,y,z;
 
 	queue<int> q;
 	for(i=1;i<=n;i++) dis[i]=1e9;
 	memset(vis,0,sizeof(vis));
    dis[1]=0;
 	q.push(1);
 	
 	while(q.empty()==0){
 	 	x=q.front(),q.pop(); vis[x]=0;
 	 	
 	 	for(i=hd[x];i;i=nxt[i]){
 	 		y=go[i],z=w[i];
 	 		if(dis[y]>dis[x]+z&&md>=val[y]){
 	 			dis[y]=dis[x]+z;
 	 			if(vis[y]==0) q.push(y),vis[y]=1; 
 	 		}
 	 	}
 	}
 	return dis[n]<K;
 }
 signed main(){
 	int i,x,y,z,md,t,l=0,r=0;
 	 cin>>n>>m>>K;
 	for(i=1;i<=n;i++) cin>>val[i],r=max(r,val[i]);
 	l=max(val[1],val[n]);
 	 
 	for(i=1;i<=m;i++) cin>>x>>y>>z,add(x,y,z),add(y,x,z);
 	
 	 if (!chk(1e9)){ cout<<"AFK" ; return 0;}
	   
 	while(l<=r){
 	   md=(l+r)/2;
 	   if(chk(md)) r=md-1; else l=md+1;
 	}
 	cout<<l;
 }
 
 
 

 

标签：瑞玛,val,int,血量,P1462,奥格,dis
From： https://www.cnblogs.com/towboa/p/17208240.html