Cod sursa(job #2077194)

Utilizator flibiaVisanu Cristian flibia Data 27 noiembrie 2017 19:54:48
Problema PScNv Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

ifstream in("pscnv.in");
ofstream out("pscnv.out");

int n, m, x, y, st, dr, mid, from, to, c;
vector <pair <int, int> > v[250100];
bool viz[250100];
queue <int> q;

bool ride(int sz){
	memset(viz, 0, sizeof viz);
	while(!q.empty()) 
		q.pop();
	q.push(from);
	viz[from] = 1;
	while(!q.empty()){
		int dad = q.front();
		if(dad == to)
			return 1;
		q.pop();
		for(auto son : v[dad])
			if(son.second <= sz && !viz[son.first]){
				viz[son.first] = 1;
				q.push(son.first);
			}
	}
	return 0;
}

int main(){
	in >> n >> m >> from >> to;
	for(int i = 1; i <= m; i++){
		in >> x >> y >> c;
		v[x].push_back({y, c});
	}
	st = 1; dr = 1000;
	while(st <= dr){
		mid = (st + dr) >> 1;
		if(ride(mid)) 
			dr = mid - 1;
		else st = mid + 1;
	}
	out << st;
}