Cod sursa(job #930633)

Utilizator razvan.popaPopa Razvan razvan.popa Data 27 martie 2013 19:13:59
Problema PScNv Scor 90
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.47 kb
#include<cstdio>
#include<list>
#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define ll long long
#define FOR(i,a,b)\
   for(int i=a; i<=b; ++i)
#define ALL(g)\
   for(typeof(g.begin()) it=g.begin(); it!=g.end(); ++it)
#define infile "pscnv.in"
#define outfile "pscnv.out"
#define nMax 250005
#define kMax 1005
using namespace std;

list < pair < int, int > > L[kMax];

int T[nMax], R[nMax];

int Cmax, Sol;

int N, M, X, Y;

void read(){
    freopen(infile, "r", stdin);

    scanf("%d %d %d %d\n", &N, &M, &X, &Y);

    char S[50];

    int x, y, cost;
    FOR(i,1,M){
    	gets(S);
    	sscanf(S, "%d %d %d", &x, &y, &cost);

    	L[cost].pb(mkp(x,y));

    	Cmax = max(Cmax, cost);
    }

    fclose(stdin);
}

int Find(int x){
    int r, y;
    for(r = x; T[r] != r; r = T[r]);

    while(T[x] != x){
        y = T[x];
        T[x] = r;
        x = y;
    }

    return r;
}

void Union(int x, int y){
    if(R[x] < R[y])
       T[x] = y;
    else
       T[y] = x;

    if(R[x] == R[y])
       R[x] ++;
}

void solve(){
    FOR(i,1,N)
        T[i] = i, R[i] = 1;

    while(Sol < Cmax && Find(X) != Find(Y)){
        Sol ++;

        ALL(L[Sol])
           Union(Find((*it).first), Find((*it).second));
    }
}

void print(){
    freopen(outfile, "w", stdout);

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

    fclose(stdout);
}

int main(){
    read();
    solve();
    print();

    return 0;
}