牛客练习赛104 D 逃亡的贝贝

https://ac.nowcoder.com/acm/contest/43058/D

思路

二分答案，对于超过当前答案并且操作后可以使用的边边权当做1，短边当做0，跑一遍最短路，非常经典的二分题

代码

#include<algorithm>
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cctype>
#include<cmath>
#include<queue>
#define ll long long
#define gc getchar
#define maxn 100005
#define maxm 200005
using namespace std;

inline ll read(){
	ll a=0;int f=0;char p=gc();
	while(!isdigit(p)){f|=p=='-';p=gc();}
	while(isdigit(p)){a=(a<<3)+(a<<1)+(p^48);p=gc();}
	return f?-a:a;
}int n,m,S,T,k;
ll l,r,ans;

struct ahaha1{
	ll w;int to,next;
}e[maxm<<1];int tot,head[maxn];
inline void add(int u,int v,ll w){
	e[tot].w=w,e[tot].to=v,e[tot].next=head[u];head[u]=tot++;
}

inline ll chu(ll x){
	return ceil(114.0*x/514);
}

struct ahaha{
	int d,id;
	inline bool friend operator<(const ahaha x,const ahaha y){
		return x.d>y.d;
	}
};
priority_queue<ahaha>q;

int d[maxn];
inline int pan(int maxa){
	for(int i=1;i<=n;++i)d[i]=k+1;
	priority_queue<ahaha>q1;
	swap(q,q1);d[S]=0;
	q.push((ahaha){0,S});
	/*for(int i=head[S];~i;i=e[i].next){
		int v=e[i].to;
		if(chu(e[i].w)>maxa)continue;
		if(e[i].w>maxa)d[v]=1,q.push((ahaha){1,v});
		else d[v]=0,q.push((ahaha){0,v});
	}*/
	while(!q.empty()){
		ahaha a=q.top();q.pop();
		int u=a.id;
		for(int i=head[u];~i;i=e[i].next){
			int v=e[i].to;if(d[v]<=a.d)continue;
			if(e[i].w>maxa){
				if(a.d==k||chu(e[i].w)>maxa)continue;
				if(d[v]<=a.d+1)continue;
				if(v==T)return 1;
				d[v]=a.d+1;
				q.push((ahaha){d[v],v});
			}
			else{
				if(d[v]<=a.d)continue;
				if(v==T)return 1;
				d[v]=a.d;
				q.push((ahaha){a.d,v});
			}
		}
	}
	return d[T]<=k;
}

int main(){memset(head,-1,sizeof head);
	n=read();m=read();S=read();T=read();k=read();
	for(int i=1;i<=m;++i){
		int u=read(),v=read();ll w=read();
		add(u,v,w);add(v,u,w);
		r=max(r,w);
	}
	ans=-1;
	if(S==T)r=0,ans=0;
	l=1;
	while(l<=r){
		int mid=l+r>>1;
		if(pan(mid))ans=mid,r=mid-1;
		else l=mid+1;
	}
	if(ans==-1){
		puts("I really need TS1's time machine again!");
		return 0;
	}
	printf("%lld\n",ans);
	return 0;
}