Cod sursa(job #1501082)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 12 octombrie 2015 23:18:32
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.83 kb
#include <fstream>
#include <algorithm>
using namespace std;

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

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

const int DIM = 250006;
int n, m, x, y, t[DIM];
str v[2 * DIM];

bool cmp(str a, str b)
{
    return a.z<b.z;
}

int find(int x)
{
    if(x != t[x])
        t[x] = find(t[x]);

    return t[x];
}

int main()
{
    fin >> n >> m >> x >> y;
    for(int i = 1; i<=m; i++)
        fin >> v[i].x >> v[i].y >> v[i].z;

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

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

    for(int i = 1; i <= m; i ++)
    {
        if(find(v[i].x) != find(v[i].y))
            t[t[v[i].x]] = t[v[i].y];

        if(find(x) == find(y))
        {
            fout << v[i].z;
            break;
        }
    }

    return 0;
}