Cod sursa(job #2670862)

Utilizator Silviu.Stancioiu@gmail.comSilviu Stancioiu [email protected] Data 10 noiembrie 2020 19:52:15
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.98 kb
#include <algorithm>
#include <fstream>

constexpr auto max_n = 250005;
constexpr auto max_m = 500005;

using namespace std;

struct edge
{
    int a, b, c;
} edges[max_m];

ifstream fin("pscnv.in");
ofstream fout("pscnv.out");
int n, m, x, y;
int parents[max_n];

int get_parent(const int node)
{
    if (parents[node] != node)
        parents[node] = get_parent(parents[node]);

    return parents[node];
}

int main()
{
    fin >> n >> m >> x >> y;
    for (auto i = 0; i < m; i++)
        fin >> edges[i].a >> edges[i].b >> edges[i].c;

    sort(edges, edges + m, [](const edge a, const edge b)
    {
        return a.c < b.c;
    });

    for (auto i = 1; i <= n; i++)
        parents[i] = i;

    for (auto edg : edges)
    {
        if (get_parent(edg.a) != get_parent(edg.b))
            parents[edg.b] = edg.a;
        if (get_parent(x) == get_parent(y))
        {
            fout << edg.c;
            return 0;
        }
    }

    return 0;
}