Cod sursa(job #951068)

Utilizator antonioteoZait Teodor Antonio antonioteo Data 19 mai 2013 09:30:19
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.53 kb
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define dim 8192
using namespace std;
const char iname[] = "pscnv.in";
const char oname[] = "pscnv.out";
struct muchie{int x, y, cost; muchie(){}; muchie(int X, int Y, int Z){x = X; y = Y; cost = Z;};}Arc;
vector <muchie> v;
vector <muchie> :: iterator it, fin;
int x;
char ax[dim];
int pz;
inline void cit(int &x){
    x = 0;
    while (ax[pz] < '0' || ax[pz] > '9')
        if (++pz == dim)
            fread (ax, 1, dim, stdin), pz = 0;
    while (ax[pz] >= '0' && ax[pz] <= '9'){
        x = x * 10 + ax[pz] - '0';
        if (++pz == dim)
            fread (ax, 1, dim, stdin), pz = 0;
    }
}
struct cmp{
	bool operator()(const muchie &A, const muchie &B) const
	{
		if (A.cost < B.cost) return 1;
		return 0;
	};
};
int N, M, A, B, i, ANS;
int t[250004];
inline int find(int i)
{
	if (t[i] != i) t[i] = find(t[i]);
	return t[i];
}
inline int uneste(int i, int j)
{
	i = find(i); j = find(j);
	if (i == j) return 0;
	t[i] = j;
	return 1;
}
int main(){
	freopen(iname,"r",stdin);
	freopen(oname,"w",stdout);
	cit(N); cit(M); cit(A); cit(B);
	for (i = 1; i <= N; ++i) t[i] = i;
	while (M--){
		cit(Arc.x); cit(Arc.y); cit(Arc.cost);
		v.push_back(Arc);
	}
	sort (v.begin(), v.end(), cmp());
	it = v.begin(), fin = v.end();
	while (find(A) != find(B) && it != fin){
		Arc = *it;
		if (find(Arc.x) != find(Arc.y)){
			uneste(Arc.x, Arc.y);
			ANS = max(ANS, Arc.cost);
		}
		++it;
	}
	printf("%d\n", ANS);
	return 0;
}