poj1797

思路是二分答案+bfs

nlogn

#include<iostream>
#include<queue>
#include<algorithm>
#include<cstring>
#define int long long
using namespace std;
const int maxn = 100100;
int vis[maxn];
struct node{
	int to, w;
};
vector<node > vec[maxn];
int n, m; 
bool check(int mid) {
	queue< int> que;
	memset(vis, 0, sizeof vis); que.push(1);
	while(!que.empty()) {
		int index = que.front(); vis[index] = 1; que.pop(); 
		for(int i=0; i<vec[index].size(); ++i) {
			if(vis[vec[index][i].to] || vec[index][i].w > mid) continue;
			que.push(vec[index][i].to);
		}
	}
	if(vis[n]) {
		return true;
	} else {
		return false;
	}
}
signed main() {
	int c; cin >> c;
	cout << "Scenario #" << c << endl;
	cin >> n >> m;
	int l = 0, r = 0;
	for(int i=1; i<=m; ++i) {
		int u, v, w; cin >> u >> v >> w; r = max(r, w);
		vec[u].push_back({v, w});
		vec[v].push_back({u, w});
	}
	int mid, ans = r;
	while(l <= r) {
		mid = l + r >> 1;
		if(check(mid)) {
			r = mid-1;
			ans = mid;
		} else {
			l = mid+1;
		}
	} 
	cout << ans;
	return 0;
}