Cod sursa(job #2479265)

Utilizator PredescuSebastianIonPredescu Sebastian Ion PredescuSebastianIon Data 23 octombrie 2019 17:01:57
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.71 kb
#include <bits/stdc++.h>
#define pb push_back

using namespace std;

ifstream f("pscnv.in");
ofstream g("pscnv.out");
const int bsize=(1<<20);
int n,m,x,y,pos=0;
int sol[250002],rep[250002],a[250002];
char ch[bsize+1];
vector <pair <int, pair <int, int> > > v;
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 search_micule_ponei(int nod)
{
    int val=nod;
    int aux;
    while(rep[val])
    {
        val=rep[val];
    }
    while(nod!=val)
    {
        aux=rep[nod];
        rep[nod]=val;
        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 xrep=search_micule_ponei(v[i].second.first);
        int yrep=search_micule_ponei(v[i].second.second);
        if(xrep!=yrep)
        {
            rep[yrep]=xrep;
        }
        xrep=search_micule_ponei(x);
        yrep=search_micule_ponei(y);
        if(xrep==yrep)
        {
            cout<<v[i].first;
            return 0;
        }
    }
    return 0;
}