Pagini recente » Cod sursa (job #147616) | Cod sursa (job #1901459) | Cod sursa (job #1980241) | Cod sursa (job #472611) | Cod sursa (job #379273)
Cod sursa(job #379273)
#include <algorithm>
#include <vector>
using namespace std;
#define pb push_back
#define mp make_pair
#define DIM 250005
#define sc second
#define fs first
vector <pair <int,pair <int,int> > > a;
int p[DIM],r[DIM];
int n,m,s,d;
void read ()
{
int i,x,y,z;
scanf ("%d%d%d%d",&n,&m,&s,&d);
for (i=1; i<=m; ++i)
{
scanf ("%d%d%d",&x,&y,&z);
a.pb (mp (z,mp (x,y)));
}
}
void unite (int x,int y)
{
if (r[x]<r[y])
p[x]=y;
else
p[y]=x;
if (r[x]==r[y])
++r[x];
}
int find (int x)
{
if (x!=p[x])
p[x]=find (p[x]);
return p[x];
}
void solve ()
{
int i;
sort (a.begin (),a.end ());
for (i=1; i<=n; ++i)
p[i]=i;
for (i=0; i<m; ++i)
{
if (find (a[i].sc.fs)!=find (a[i].sc.sc))
unite (find (a[i].sc.fs),find (a[i].sc.sc));
if (find (s)==find (d))
{
printf ("%d",a[i].fs);
return ;
}
}
}
int main ()
{
freopen ("pscnv.in","r",stdin);
freopen ("pscnv.out","w",stdout);
read ();
solve ();
return 0;
}