Cod sursa(job #1511610)

Utilizator StarGold2Emanuel Nrx StarGold2 Data 26 octombrie 2015 22:47:07
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.5 kb
#include <cstdio>
#include <cstring>
#include <algorithm>

#define DIM 250010
#define cost first
#define node1 second.first
#define node2 second.second
using namespace std;

int startNode, finishNode;
int nrNodes, nrEdges, value1, value2, Root[DIM];
pair <int, pair <int, int> > Edges[DIM*2];

inline int getRoot (int node)
{
    return (Root[node] < 0) ? node : getRoot (Root[node]);
}

int main ()
{
    freopen ("pscnv.in" ,"r", stdin );
    freopen ("pscnv.out","w", stdout);

    scanf ("%d %d", &nrNodes, &nrEdges);
    scanf ("%d %d", &startNode, &finishNode);
    memset (Root, -1, sizeof (Root));

    for (int i = 1; i <= nrEdges; i ++)
    {
        scanf ("%d", &Edges[i].node1);
        scanf ("%d", &Edges[i].node2);
        scanf ("%d", &Edges[i].cost );
    }

    sort (Edges + 1, Edges + nrEdges + 1);

    for (int i = 1; i <= nrEdges; i ++)
    {
        value1 = getRoot (Edges[i].node1);
        value2 = getRoot (Edges[i].node2);

        if (value1 != value2)
        {
            switch (Root[value1] - Root[value2] <= 0)
            {
                case 1: { Root[value1] += Root[value2]; Root[value2] = value1; break; }
                case 0: { Root[value2] += Root[value1]; Root[value1] = value2; break; }
            }
        }

        if (getRoot (startNode) == getRoot (finishNode))
        {
            printf ("%d\n", Edges[i].cost);
            break;
        }
    }

    fclose (stdin );
    fclose (stdout);

    return 0;
}