Cod sursa(job #3145983)

Utilizator andrei_marciucMarciuc Andrei andrei_marciuc Data 17 august 2023 18:35:03
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#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;
}