Pagini recente » Cod sursa (job #1156820) | Cod sursa (job #1452970) | Cod sursa (job #2543281)
#include <bits/stdc++.h>
using namespace std;
const int NMAX = 250005;
const int MMAX = 500005;
int N, M, X, Y;
struct Edge
{
int x, y, cost;
};
Edge edges[MMAX];
int father[NMAX];
void Union(int x, int y)
{
father[y] = x;
}
int Find(int x)
{
int root = x, cx;
while (father[root] != 0)
root = father[root];
while (x != root)
{
cx = father[x];
father[x] = root;
x = cx;
}
return root;
}
int main()
{
ifstream fin("pscnv.in");
ofstream fout("pscnv.out");
fin >> N >> M >> X >> Y;
for (int i = 1;i <= M;++i)
{
int u, v, c;
fin >> u >> v >> c;
edges[i] = {u, v, c};
}
sort(edges + 1, edges + M + 1, [&](Edge a, Edge b)
{
return a.cost < b.cost;
});
int answer;
for (int i = 1;i <= M;++i)
{
int x = edges[i].x;
int y = edges[i].y;
x = Find(x);
y = Find(y);
if (x != y)
{
Union(x, y);
x = Find(X);
y = Find(Y);
if (x == y)
{
answer = edges[i].cost;
break;
}
}
}
fout << answer << "\n";
fin.close();
fout.close();
return 0;
}