Pagini recente » Cod sursa (job #1104024) | Cod sursa (job #2002202) | Cod sursa (job #1617356) | Cod sursa (job #359) | Cod sursa (job #3145983)
#include <algorithm>
#include <stdio.h>
#include <vector>
struct muchii {
int x, y, cost;
};
int dad[250'010];
int n, m;
int x, y;
int Tata(int x) {
if(dad[x] == x)
return x;
return dad[x] = Tata(dad[x]);
}
int main()
{
freopen("pscnv.in", "r", stdin);
freopen("pscnv.out", "w", stdout);
scanf("%d %d %d %d", &n, &m, &x, &y);
std::vector<muchii> muchie(m);
for(int i = 0; i < m; i++)
scanf("%d %d %d", &muchie[i].x, &muchie[i].y, &muchie[i].cost);
std::sort(muchie.begin(), muchie.end(), [](const muchii& A, const muchii& B) {
return A.cost < B.cost;
} );
for(int i = 1; i <= n; i++)
dad[i] = i;
int poz = 0;
int A = dad[x]; // x
int B = dad[y]; // y
while(A != B) {
if(Tata(muchie[poz].x) != Tata(muchie[poz].y))
dad[muchie[poz].x] = muchie[poz].y;
++poz;
A = Tata(x);
B = Tata(y);
}
printf("%d\n", muchie[poz - 1].cost);
return 0;
}