Cod sursa(job #1734324)

Utilizator pas.andreiPopovici Andrei-Sorin pas.andrei Data 27 iulie 2016 01:41:55
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.63 kb
#include <fstream>
#include <algorithm>
#define NMAX 500005

using namespace std;

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

int p[NMAX];

struct muchie {
	int x,y,c;
} v[NMAX];
bool comp(muchie A, muchie B) { return A.c<B.c; }
int findSet(int x) {
	if(x==p[x]) return x;
	return p[x]=findSet(p[x]);
}

int main() {
	int n,m,i,a,b,nr=0;

	fin>>n>>m>>a>>b;
	for(i=1;i<=n;++i) p[i]=i;
	for(i=0;i<m;++i) fin>>v[i].x>>v[i].y>>v[i].c;

	sort(v,v+m,comp);

	while(findSet(a)!=findSet(b)) {
		if(findSet(v[nr].x) != findSet(v[nr].y)) p[v[nr].y]=p[v[nr].x];
		++nr;
	}

	fout<<v[nr-1].c;

	return 0;
}