Pagini recente » Cod sursa (job #2983014) | Cod sursa (job #1502017) | Cod sursa (job #3286641) | Cod sursa (job #1612512) | Cod sursa (job #2400360)
#include<bits/stdc++.h>
using namespace std;
const int maxN=250005;
const int dim=(1e5);
char buff[dim+5];
int pos=0,n,m,start,finish;
int t[maxN];
int sol;
struct tip
{
int x,y,z;
};
bool cmp(tip a,tip b)
{
return a.z<b.z;
}
int xroot,yroot;
tip edges[2*maxN];
inline void read(int &nr)
{
nr=0;
while(!isdigit(buff[pos]))
{
pos++;
if(pos==dim)
{
pos=0;
fread(buff,1,dim,stdin);
}
}
while(isdigit(buff[pos]))
{
nr=nr*10+buff[pos]-'0';
pos++;
if(pos==dim)
{
pos=0;
fread(buff,1,dim,stdin);
}
}
}
inline int getroot(int x)
{
int y=x;
while(t[y]>0)
{
y=t[y];
}
int z=x;
while(z!=y)
{
int aux=t[z];
t[z]=y;
z=aux;
}
return y;
}
inline void unite(int x,int y)
{
int xr=getroot(x);
int yr=getroot(y);
if(t[xr]<t[yr])
{
t[xr]+=t[yr];
if(xroot==yr) xroot=yr;
if(yroot==yr) yroot=xr;
t[yr]=xr;
}
else
{
t[yr]+=t[xr];
if(xroot==xr) xroot=yr;
if(yroot==xr) yroot=yr;
t[xr]=yr;
}
}
inline void add_edge(int i)
{
int x=edges[i].x;
int y=edges[i].y;
int z=edges[i].z;
unite(x,y);
}
int main()
{
freopen("pscnv.in","r",stdin);
freopen("pscnv.out","w",stdout);
fread(buff,1,dim,stdin);
read(n);
read(m);
read(start);
read(finish);
for(int i=1;i<=n;i++)
t[i]=-1;
xroot=start;
yroot=finish;
for(int i=1;i<=m;i++)
{
int x,y,z;
read(x);
read(y);
read(z);
edges[i]={x,y,z};
}
sort(edges+1,edges+m+1,cmp);
int cnt=1; //the current edge
while(xroot!=yroot)
{
sol=edges[cnt].z;
while(edges[cnt].z==sol)
{
add_edge(cnt);
cnt++;
}
}
printf("%d\n",sol);
return 0;
}