Cod sursa(job #752087)

Utilizator GrimpowRadu Andrei Grimpow Data 27 mai 2012 19:37:55
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.16 kb
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cmath>

using namespace std;

#define file_in "pscnv.in"
#define file_out "pscnv.out"

#define nmax 505012

int n,m;
int x,y;
int tata[nmax];
struct pac
{
    int a,b,c;
}
p[nmax];

void citire()
{
    freopen(file_in,"r",stdin);
    freopen(file_out,"w",stdout);

    scanf("%d %d %d %d", &n, &m, &x, &y);
    int i;
    for (i=1;i<=m;++i)
         scanf("%d %d %d", &p[i].a,&p[i].b, &p[i].c);

}

int cmp(pac x,pac y)
{
    return x.c<y.c;
}

int father(int x)
{
    if (tata[x]!=x)
         tata[x]=father(tata[x]);
         return tata[x];
}

void unite(int i, int j)
{
   tata[tata[i]]=tata[j];
}

void solve()
{
    int i,t1,t2;

    sort(p+1,p+m+1,cmp);
    for (i=1;i<=n;++i)
           tata[i]=i;
    for (i=1;i<=m;++i)
    {
        t1=father(p[i].a);
        t2=father(p[i].b);
        if (t1!=t2)
        {
            unite(p[i].a,p[i].b);
        }
        if (father(x)==father(y))
        {
            printf("%d\n", p[i].c);
            exit(0);
        }
    }
}

int main()
{
    citire();
    solve();

    fclose(stdin);
    fclose(stdout);

    return 0;
}