Cod sursa(job #2922332)

Utilizator toma_ariciuAriciu Toma toma_ariciu Data 7 septembrie 2022 22:33:16
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.1 kb
/// Preset de infoarena
#include <fstream>
#include <algorithm>

using namespace std;

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

struct muchie {
    int nod1, nod2, cost;
}lm[500005];

int n, m, root[250005], depth[250005];

int findroot(int x)
{
    if(root[x] == 0)
        return x;
    return findroot(root[x]);
}

void join(int x, int y)
{
    if(depth[x] == depth[y])
        root[x] = y, depth[y]++;
    if(depth[x] < depth[y])
        root[x] = y;
    if(depth[x] > depth[y])
        root[y] = x;
}

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

int main()
{
    int x, y;
    fin >> n >> m >> x >> y;
    for(int i = 1; i <= m; i++)
        fin >> lm[i].nod1 >> lm[i].nod2 >> lm[i].cost;
    sort(lm + 1, lm + m + 1, cmp);
    for(int i = 1; i <= m; i++)
    {
        int rx = findroot(lm[i].nod1), ry = findroot(lm[i].nod2);
        if(rx == ry)
            continue;
        join(rx, ry);
        if(findroot(x) == findroot(y))
        {
            fout << lm[i].cost << '\n';
            return 0;
        }
    }
    return 0;
}