Cod sursa(job #1491391)

Utilizator nimicLeoveanu Mihaita Alexandru nimic Data 25 septembrie 2015 10:41:24
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.87 kb
#include<fstream>
#include<algorithm>
using namespace std;
ifstream in("pscnv.in");
ofstream out("pscnv.out");

struct psc
{
    int x, y, cost;
};

const int nmax = 250006;
int n, m, x, y, tata[nmax];
psc v[2 * nmax];
 
bool cmp(psc a, psc b)
{
    return a.cost<b.cost;
}
 
int find(int x)
{
    if(x!=tata[x])
        tata[x] = find(tata[x]);

    return tata[x];
}
 
int main()
{
    int player_unu=0;

    in>>n>>m>>x>>y;
    for(int i = 1; i<=m; i++)
        in>>v[i].x>>v[i].y>>v[i].cost;

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

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

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

        if(find(x)==find(y))
        {
            out<<v[i].cost<<'\n';
            break;
        }
    }

    return player_unu;
}