Cod sursa(job #2696024)

Utilizator TheSharkCristian-Andrei Ionescu TheShark Data 15 ianuarie 2021 02:34:58
Problema PScNv Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.71 kb
#include <fstream>
#include <algorithm>
#define NMAX 530000
using namespace std;

ifstream in("pscnv.in");
ofstream out("pscnv.out");

struct edge
{
	int x, y, c;
}v[NMAX];

int i, n, m, x, y, w[NMAX];

int rec(int i)
{
	if (i != w[i]) {
		w[i] = rec(w[i]);
	}

	return w[i];
}

int main()
{

	in >> n >> m >> x >> y;
	for (i = 1; i <= m; i++) {
		in >> v[i].x >> v[i].y >> v[i].c;
	}

	sort(v + 1, v + m + 1, [](edge a, edge b) -> bool
		{
			return a.c < b.c;
		});

	for (i = 1; i <= n; i++) {
		w[i] = i;
	}

	for (i = 1; i <= m; i++)
	{
		if (rec(v[i].x) != rec(v[i].y))
			w[v[i].x] = v[i].y;
		if (rec(x) == rec(y))
		{
			out << v[i].c;
			return 0;
		}
	}

	return 0;
}