Pagini recente » Cod sursa (job #1080127) | Cod sursa (job #380859) | Cod sursa (job #3216156) | Cod sursa (job #471028) | Cod sursa (job #407908)
Cod sursa(job #407908)
#include <iostream>
#include <fstream>
#include <vector>
using namespace std;
int N, M, x, y;
int Arb[250001], H[250001];
vector<pair<int, pair<int, int> > > G;
int CC(int nod) {
while(Arb[nod]!=nod) {
nod=Arb[nod];
}
return nod;
}
void Un(int p, int q) {
if(H[p]>H[q]) {
Arb[q]=p;
}
else {
Arb[p]=q;
}
if(H[p]==H[q]) { H[p]++; }
}
int main() {
fstream f1, f2;
int i, j, p, q, c, cost;
f1.open("pscnv.in", ios::in);
f1>>N>>M>>x>>y;
for(i=1; i<=M; i++) {
f1>>p>>q>>c;
G.push_back(make_pair(c, make_pair(p, q)));
}
f1.close();
for(i=1; i<=N; i++) {
Arb[i]=i; H[i]=1;
}
sort(G.begin(), G.end()); //sortez dupa cost
for(vector<pair<int, pair<int, int> > >::iterator it=G.begin(); it!=G.end(); it++) {
if(CC((*it).second.first)!=CC((*it).second.second)) {
Un((*it).second.first, (*it).second.second);
}
if(CC(x)==CC(y)) {
cost=(*it).first; break;
}
}
f2.open("pscnv.out", ios::out);
f2<<cost<<endl;
f2.close();
return 0;
}