Cod sursa(job #2918203)

Utilizator tomaionutIDorando tomaionut Data 10 august 2022 14:39:58
Problema PScNv Scor 80
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 0.93 kb
#include <bits/stdc++.h>
#define INF 1e9
using namespace std;

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

struct edge
{
	int u, v, c;
	bool operator < (const edge alt) const
	{
		return c < alt.c;
	}
}v[250005];

struct DSU
{
	vector <int> a;

	DSU(int N)
	{
		a.resize(N + 2);
	}

	void Unite(int x, int y)
	{
		a[y] = x;
	}

	int Find(int x)
	{
		int rad = x, y;
		while (a[rad])
			rad = a[rad];

		while (x != rad)
		{
			y = a[x];
			a[x] = rad;
			x = y;
		}

		return rad;
	}
};

int n, m, X, Y;

int main()
{
	int i, j, c;
	fin >> n >> m >> X >> Y;
	for (i = 1; i <= m; i++)
		fin >> v[i].u >> v[i].v >> v[i].c;

	DSU tree(n);
	sort(v + 1, v + m + 1);
	for (i = 1; i <= m; i++)
	{
		if (tree.Find(v[i].u) != tree.Find(v[i].v))
			tree.Unite(v[i].u, v[i].v);

		if (tree.Find(X) == tree.Find(Y))
		{
			fout << v[i].c << "\n";
			return 0;
		}
	}

	return 0;
}