Pagini recente » Cod sursa (job #1232697) | Cod sursa (job #1461270) | Cod sursa (job #3176071) | Cod sursa (job #2397018) | Cod sursa (job #2918203)
#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;
}