Pagini recente » Cod sursa (job #1965553) | Cod sursa (job #2968353) | Cod sursa (job #1857974) | Cod sursa (job #2528976) | Cod sursa (job #379980)
Cod sursa(job #379980)
#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;
}