Cod sursa(job #379980)

Utilizator victor.ionescuIonescu Victor Cristian victor.ionescu Data 4 ianuarie 2010 15:49:17
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.84 kb
#include <fstream>
#include <algorithm>
#include <cstring>
using namespace std;
int N,M,X,Y;
struct muchie { int x,y,cost; } v[500010];
int P[250010],W[250010];

inline bool cmp(const muchie &A, const muchie &B){
	return A.cost<B.cost;
}

int find_Set(int x){
	if (P[x]!=x) P[x]=find_Set(P[x]);
	return P[x];
}


int main(){

	ifstream fi("pscnv.in");
	fi>>N>>M>>X>>Y;
	for (int i=1;i<=M;++i)
		fi>>v[i].x>>v[i].y>>v[i].cost;
	fi.close();

	sort(v+1,v+M+1,cmp);

	for (int i=1;i<=N;++i) P[i]=i,W[i]=0;


	ofstream fo("pscnv.out");
	for (int i=1;i<=M;++i){
		int s1=find_Set(v[i].x),s2=find_Set(v[i].y);
		if (s1!=s2){
			if (W[s1]<W[s2]){
				P[s1]=s2;
			} else if (W[s1]>W[s2]){
				P[s2]=s1;
			} else {
				P[s1]=s2;
				++W[s2];
			}
		}
		int sX=find_Set(X),sY=find_Set(Y);
		if (sX==sY) { fo<<v[i].cost<<"\n"; break; }
	}
	fo.close();

	return 0;
}