二分答案+图论 例题题解 c++

题目：传送门
首先这题的 最短路 不一定是最优解，因为题目说是路径上最长的一条边的值最小。
所以改良一个 BFS 求最短路（不就是接近SPFA吗）结合二分答案，求出结果。
AC代码：

#include<bits/stdc++.h>
using namespace std;
#define MAXN 50010
#define RI register int
int end[MAXN],value[MAXN],nxt[MAXN],head[MAXN];
int q[MAXN],n,m,s,t,front,last,r=-999,l;
bool vis[MAXN];
void init(){
	memset(nxt,-1,sizeof(nxt));
	memset(head,-1,sizeof(head));
	scanf("%d%d%d%d",&n,&m,&s,&t);
	for(RI i=1;i<=m;i++){
		int a,b,c;
		scanf("%d%d%d",&a,&b,&c);
		value[i*2]=c;
		end[i*2]=b;
		nxt[i*2]=head[a];
		head[a]=i*2;
		value[i*2+1]=c;
		end[i*2+1]=a;
		nxt[i*2+1]=head[b];
		head[b]=i*2+1;
		if(c>r)r=c;
	}
}
bool check(int x){
	memset(vis,0,sizeof(vis));
	front=last=1;
	q[1]=s;vis[s]=1;
	while(front<=last){
		int v=head[q[front]];
		while(v!=-1){
			if(!vis[end[v]]&&value[v]<=x){
				q[++last]=end[v];
				vis[end[v]]=1;
			}
			v=nxt[v];
		}
		front++;
	}
	return vis[t];
}
int main(){
	init();
	r++;l=1;
	while(l<r){
		int mid=(l+r)>>1;
		if(check(mid)){
			r=mid;
		}else l=mid+1;
	}
	printf("%d",l);
	return 0;
} 

我这次竟然没有用链式前向星 …

谢谢阅读

本文地址：https://blog.csdn.net/SB_zero_mark/article/details/109269984