Cod sursa(job #2671997)

Utilizator SirbuSirbu Ioan Sirbu Data 12 noiembrie 2020 21:58:05
Problema PScNv Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <bits/stdc++.h>

using namespace std;


ifstream fin("pscnv.in");
ofstream fout("pscnv.out");

struct muchie {
    int x;
    int y;
    int cost;
};
muchie muchii[250002];

int parinti[250002];

int get_parinte(int node) {

    if (parinti[node] != node)
        parinti[node] = get_parinte(parinti[node]);

    return parinti[node];
}

bool cmp (muchie a, muchie b) {
    return a.cost < b.cost;
}

int main()
{
    int n, m, a, b;
    fin >> n >> m >> a >> b;

    for (int i = 1; i <= m; ++i)
        fin >> muchii[i].x >> muchii[i].y >> muchii[i].cost;

    sort(muchii + 1, muchii + m + 1, cmp);

    for (int i = 1; i <= n; ++i)
        parinti[i] = i;

    int minim = -1;

    for (auto edge : muchii) {
        if (get_parinte(edge.x) != get_parinte(edge.y))
            parinti[edge.y] = edge.x;
        if(get_parinte(a) == get_parinte(b) && minim < 0)
            minim = edge.cost;
    }
    fout << minim;
    return 0;
}