Pagini recente » Cod sursa (job #1918121) | Cod sursa (job #559854) | Cod sursa (job #2414603) | Cod sursa (job #1107021) | Cod sursa (job #2695196)
#include <iostream>
#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() {
FILE *f1=fopen("pscnv.in", "r"), *f2=fopen("pscnv.out", "w");
int i, j, p, q, c, cost;
fscanf(f1, "%d%d%d%d", &N, &M, &x, &y);
for(i=1; i<=M; i++) {
fscanf(f1, "%d%d%d", &p, &q, &c);
G.push_back(make_pair(c, make_pair(p, q)));
}
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++) {
p=CC((*it).second.first);
q=CC((*it).second.second);
if(p!=q) {
Un(p, q);
}
if(CC(x)==CC(y)) {
cost=(*it).first; break;
}
}
fprintf(f2, "%d\n", cost);
fclose(f1); fclose(f2);
return 0;
}