Pagini recente » Cod sursa (job #3286082) | Cod sursa (job #1257592) | Cod sursa (job #1072829) | Cod sursa (job #1224546) | Cod sursa (job #2922332)
/// Preset de infoarena
#include <fstream>
#include <algorithm>
using namespace std;
ifstream fin("pscnv.in");
ofstream fout("pscnv.out");
struct muchie {
int nod1, nod2, cost;
}lm[500005];
int n, m, root[250005], depth[250005];
int findroot(int x)
{
if(root[x] == 0)
return x;
return findroot(root[x]);
}
void join(int x, int y)
{
if(depth[x] == depth[y])
root[x] = y, depth[y]++;
if(depth[x] < depth[y])
root[x] = y;
if(depth[x] > depth[y])
root[y] = x;
}
bool cmp(muchie a, muchie b)
{
return a.cost < b.cost;
}
int main()
{
int x, y;
fin >> n >> m >> x >> y;
for(int i = 1; i <= m; i++)
fin >> lm[i].nod1 >> lm[i].nod2 >> lm[i].cost;
sort(lm + 1, lm + m + 1, cmp);
for(int i = 1; i <= m; i++)
{
int rx = findroot(lm[i].nod1), ry = findroot(lm[i].nod2);
if(rx == ry)
continue;
join(rx, ry);
if(findroot(x) == findroot(y))
{
fout << lm[i].cost << '\n';
return 0;
}
}
return 0;
}