Cod sursa(job #378881)

Utilizator ProtomanAndrei Purice Protoman Data 29 decembrie 2009 21:05:15
Problema PScNv Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 0.82 kb
#include <algorithm>
#include <iostream>
#include <fstream>

#define MAX 500010
#define mp make_pair
#define f first
#define s second

using namespace std;

int n, m, x, y;
int tata[MAX];
pair <int, pair <int, int> > vctDr[MAX];

inline int rad(int x)
{
	if (tata[x] != x)
		tata[x] = rad(tata[x]);
	return tata[x];
}

int main()
{
	ifstream cin("pscnv.in");
	ofstream cout("pscnv.out");

	cin >> n >> m >> x >> y;

	for (int i = 1; i <= m; i++)
		cin >> vctDr[i].s.f >> vctDr[i].s.s >> vctDr[i].f;

	sort(vctDr + 1, vctDr + 1 + m);

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

	for (int i = 1; i <= m; i++)
	{
		if (rad(vctDr[i].s.f) != rad(vctDr[i].s.s))
			tata[vctDr[i].s.f] = tata[vctDr[i].s.s];

		if (rad(x) == rad(y))
		{
			cout << vctDr[i].f << '\n';

			return 0;
		}
	}
}