题目

#include <bits/stdc++.h>
const int maxn=20005;
int n,m,s,t;
struct node{
	int u,v,w;
}a[maxn];

int q[maxn];
bool vis[maxn];

bool is_valid(int xx,int x){
	if(a[xx].w>x) return false;
	if(vis[xx]) return false;
	return true;
}

bool bfs(int x){
	memset(vis+1,false,sizeof(vis));
	int l=1,r=1;
	q[r]=s;
	vis[s]=true;
	r++;
	
	while(l<r){
		int xx=a[q[l]].u;
		if(is_valid(xx,x)){
			q[r]=a[xx].v;
			vis[a[xx].v]=true;
			r++;
		}
		xx=a[xx].v;
		l++;
	}
	return vis[t];
}


int check(int l,int r){
	while(l<r){
		int mid=(l+r)>>1;
		if(bfs(mid)) r=mid;
		else l=mid+1;
	}
	return l;
}


int main(){
	scanf("%d%d%d%d",&n,&m,&s,&t);
	int maxa=-1;
	for(int i=1;i<=m;i++){
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		a[i].u=u,a[i].v=v,a[i].w=w;
		if(w>maxa) maxa=w;
	}
	printf("%d\n",check(1,maxa));
	return 0;
}

dalao求调

写的比较烂，勿喷

我只是一个平平无奇的xxs