201703-4 地铁维修

思路

这道题是求最大值最小，所以很明显又是要用二分。自己没注意到是因为没有注意到所选边数小于等于n这个事，所以理解题意呀！
每次二分得到一个距离mid，如果能选不超过n条边，使得每条边的权值都小于mid，那么这个值就可以选。
由于这里只涉及边的个数，所以所有边的权都变成1了，所以用bfs+松弛操作就好了。

代码：

#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
const int N = 1e5 + 5;
const int M = 4*N;
int h[N], e[M], ne[M], w[M], idx;
int d[N];
void add(int a, int b ,int c){
	 e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx++;
}
int n,m;
inline int read(){//读优化，没有这个90分
    	int x=0,f=1;
    	char c=getchar();//scanf函数比getchar函数慢不少，当需要大量输入数据时可考虑优化
    	while(c>'9'||c<'0'){
    		if(c=='-') f=-f;
    		c=getchar();
    	}
    	while(c>='0'&&c<='9'){
    		x=x*10+c-'0';
    		c=getchar();
    	}
    	return x*f;
}
int bfs(int mid){
	memset(d, 0x3f, sizeof(d));
	queue q;
	d[1] = 0;
	q.push(1);
	while(q.size()){
		int t = q.front();
		q.pop();
		for(int i = h[t]; i != -1;i = ne[i]){
			if(w[i] > mid)continue;
			int j = e[i];
			if(d[j] > d[t] + 1){
				d[j] = d[t] + 1;
				q.push(j); 
			}
		}
	}
	return d[n];
}
int main(){
	memset(h, -1, sizeof(h));
	n = read(), m = read();
	while(m--){
		int a,b,c;
		a = read(), b = read(), c = read();
		add(a, b ,c);
		add(b, a, c);
	}
	int l = 0, r = 1e6;
	while(l < r){
		int mid = (l + r) / 2;
		if(bfs(mid) <= n){
			r = mid;
		}else{
			l = mid + 1;
		}
	}
	cout<