Cod sursa(job #1013278)

Utilizator gabrielinelusGabriel-Robert Inelus gabrielinelus Data 20 octombrie 2013 18:37:56
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.83 kb
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>

void scan(int &A)
{
    char c = 0;A = 0;
    do
    {
        c = fgetc(stdin);
        if('0'<=c && c<='9')
            A = A * 10 + c - 48;
    }while('0'<= c && c<='9');
}

using namespace std;
const int INF = 0x3f3f3f3f;
const int Nmax = 250005;

struct arce{
    int x;
    int y;
    int cost;
};

int N,M,fr,to; // from , to
int D[Nmax],daddy[Nmax];
vector<pair<int,int> > G[Nmax];

struct cmp{
    bool operator()(const arce A,const arce B)const
    {
        return A.cost > B.cost;
    }
};
priority_queue<arce,vector<arce>,cmp> Q;

inline int whos_ur_daddy(int nodc)
{
    if(daddy[nodc]!= nodc)
        daddy[nodc]=whos_ur_daddy(daddy[nodc]);
    return daddy[nodc];
}
inline void couple(int a,int b){daddy[daddy[a]] = daddy[b];}

void getg()
{
    scan(N),scan(M),scan(fr),scan(to);
    for(int i = 1; i <= N; ++i)daddy[i] = i;
    arce A;
    for(int i = 1; i <= M; ++i)
    {
        scan(A.x),scan(A.y),scan(A.cost);
        Q.push(A);
    }
}

void kruskal()
{
    int step = 0;
    arce A;
    while( step != N - 1)
    {
        A = Q.top();Q.pop();
        if(whos_ur_daddy(A.x)!=whos_ur_daddy(A.y))
        {
            couple(A.x,A.y);
            ++step;
            G[A.x].push_back(make_pair(A.y,A.cost));
        }
    }
}

void DFS(int nodc)
{
    vector<pair<int,int> >::iterator it;
    for(it = G[nodc].begin() ; it != G[nodc].end();++it)
        if(!D[it->first])
        {
            D[it->first] = max(D[nodc],it->second);
            DFS(it->first);
        }
}

void solve()
{
    kruskal();
    DFS(fr);
    printf("%d",D[to]);
}

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