Cod sursa(job #2543281)

Utilizator aurelionutAurel Popa aurelionut Data 10 februarie 2020 23:43:32
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.29 kb
#include <bits/stdc++.h>

using namespace std;

const int NMAX = 250005;
const int MMAX = 500005;
int N, M, X, Y;
struct Edge
{
    int x, y, cost;
};

Edge edges[MMAX];
int father[NMAX];

void Union(int x, int y)
{
    father[y] = x;
}

int Find(int x)
{
    int root = x, cx;
    while (father[root] != 0)
        root = father[root];
    while (x != root)
    {
        cx = father[x];
        father[x] = root;
        x = cx;
    }
    return root;
}

int main()
{
    ifstream fin("pscnv.in");
    ofstream fout("pscnv.out");
    fin >> N >> M >> X >> Y;
    for (int i = 1;i <= M;++i)
    {
        int u, v, c;
        fin >> u >> v >> c;
        edges[i] = {u, v, c};
    }
    sort(edges + 1, edges + M + 1, [&](Edge a, Edge b)
    {
        return a.cost < b.cost;
    });
    int answer;
    for (int i = 1;i <= M;++i)
    {
        int x = edges[i].x;
        int y = edges[i].y;
        x = Find(x);
        y = Find(y);
        if (x != y)
        {
            Union(x, y);
            x = Find(X);
            y = Find(Y);
            if (x == y)
            {
                answer = edges[i].cost;
                break;
            }
        }
    }
    fout << answer << "\n";
    fin.close();
    fout.close();
    return 0;
}