Pagini recente » Cod sursa (job #1671627) | Cod sursa (job #515805) | Cod sursa (job #2581601) | Cod sursa (job #2253258) | Cod sursa (job #406815)
Cod sursa(job #406815)
using namespace std;
#include<fstream>
#include<vector>
#include<algorithm>
#define MAX_N 250002
int h[MAX_N], tata[MAX_N], N, M, S, D;
vector<pair<int, pair<int,int> > >G;
int find(int x)
{
if(tata[x] != x) tata[x] = find(tata[x]);
return tata[x];
}
void join(int x, int y)
{
if(h[x] > h[y]) tata[y] = x;
else tata[x] = y;
if(h[x] == h[y]) ++h[x];
}
int main()
{
ifstream f("pscnv.in"); ofstream g("pscnv.out");
f>>N>>M>>S>>D;
int i,x,y,c;
for(i = 1; i <= N; ++i)
{
h[i] = 1; tata[i] = i;
}
for(i = 1; i<=M; ++i)
{
f>>x>>y>>c;
G.push_back(make_pair(c, make_pair(x,y)));
}
sort(G.begin(), G.end());
for(i = 0; i < M; ++i)
{
if ( find(G[i].second.first) != find(G[i].second.second) )
join(G[i].second.first, G[i].second.second);
if( find(S) == find(D) )
{
g<<G[i].first<<"\n";
return 0;
}
}
return 0;
}