Cod sursa(job #2479241)

Utilizator AlexandruabcdeDobleaga Alexandru Alexandruabcde Data 23 octombrie 2019 16:35:06
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.77 kb
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

ifstream f ("pscnv.in");
ofstream g ("pscnv.out");

constexpr int NMAX = 25e4 + 5;
constexpr int bsize = (1<<20);

int n, m, x, y;

vector <pair <int, pair <int, int> > > v;

int sol[NMAX];
int tata[NMAX];
int adanc[NMAX];

char ch[bsize+1];
int pos=0;

void read (int &x)
{
    while (!isdigit(ch[pos]))
    {
        pos++;
        if (pos == bsize)
        {
            pos = 0;
            fread(ch, 1, bsize, stdin);
        }
    }

    x=0;

    while (isdigit(ch[pos]))
    {
        x = x * 10 + ch[pos] - '0';
        pos++;
        if (pos == bsize)
        {
            pos = 0;
            fread(ch, 1, bsize, stdin);
        }
    }
}

int caut(int nod)
{
    int gig = nod;
    int aux;

    while (tata[gig]) gig = tata[gig];

    while (nod != gig)
    {
        aux = tata[nod];
        tata[nod] = gig;
        nod = aux;
    }

    return nod;
}

int main()
{
    freopen("pscnv.in", "r", stdin);
    freopen("pscnv.out", "w", stdout);
    fread(ch, 1, bsize, stdin);
    ios_base::sync_with_stdio(false);
    pos = 0;

    read(n);
    read(m);
    read(x);
    read(y);

    for (int i=1; i<=m; ++i)
    {
        int a, b, c;
        read(a);
        read(b);
        read(c);

        v.pb({c, {a, b}});
    }

    sort(v.begin(), v.end());

    for (int i=0; i<v.size(); ++i)
    {
        int xtata = caut(v[i].second.first);
        int ytata = caut(v[i].second.second);

        if (xtata != ytata)
            tata[ytata] = xtata;

        xtata = caut(x);
        ytata = caut(y);

        if (xtata == ytata)
        {
            cout << v[i].first;
            return 0;
        }
    }
    return 0;
}