Cod sursa(job #2479236)

Utilizator stefantagaTaga Stefan stefantaga Data 23 octombrie 2019 16:17:37
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.08 kb
#include<bits/stdc++.h>
using namespace std;

const int maxN=250005;
const int dim=(1e5);
char buff[dim+5];
int pos=0,n,m,start,finish;
int t[maxN];
int sol;

struct tip
{
    int x,y,z;
};

bool cmp(tip a,tip b)
{
    return a.z<b.z;
}
int xroot,yroot;

tip edges[2*maxN];

inline void read(int &nr)
{
    nr=0;
    while(!isdigit(buff[pos]))
    {
        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }
    }

    while(isdigit(buff[pos]))
    {
        nr=nr*10+buff[pos]-'0';
        pos++;
        if(pos==dim)
        {
            pos=0;
            fread(buff,1,dim,stdin);
        }
    }
}

inline int getroot(int x)
{
    int y=x;
    while(t[y]>0)
    {
        y=t[y];
    }
    int z=x;
    while(z!=y)
    {
        int aux=t[z];
        t[z]=y;
        z=aux;
    }

    return y;
}
inline void unite(int x,int y)
{
    int xr=getroot(x);
    int yr=getroot(y);
    if(t[xr]<t[yr])
    {
        t[xr]+=t[yr];
        if(xroot==yr) xroot=yr;
        if(yroot==yr) yroot=xr;
        t[yr]=xr;
    }
        else
    {
        t[yr]+=t[xr];
        if(xroot==xr) xroot=yr;
        if(yroot==xr) yroot=yr;
        t[xr]=yr;
    }
}

inline void add_edge(int i)
{
    int x=edges[i].x;
    int y=edges[i].y;
    int z=edges[i].z;

    unite(x,y);

}
int main()
{
    freopen("pscnv.in","r",stdin);
    freopen("pscnv.out","w",stdout);

    fread(buff,1,dim,stdin);

    read(n);
    read(m);
    read(start);
    read(finish);

    for(int i=1;i<=n;i++)
        t[i]=-1;

    xroot=start;
    yroot=finish;

    for(int i=1;i<=m;i++)
    {
        int x,y,z;
        read(x);
        read(y);
        read(z);

        edges[i]={x,y,z};
    }

    sort(edges+1,edges+m+1,cmp);

    int cnt=1; //the current edge

    while(xroot!=yroot)
    {
        sol=edges[cnt].z;
        while(edges[cnt].z==sol)
        {
            add_edge(cnt);
            cnt++;
        }
    }

    printf("%d\n",sol);

    return 0;
}