Pagini recente » Cod sursa (job #985155) | Cod sursa (job #2281784) | Cod sursa (job #1550042) | Cod sursa (job #2377819) | Cod sursa (job #1474630)
#include<bits/stdc++.h>
#define Lim 500000
#define Next (++pos==Lim)?(fin.read(Buffer,Lim),pos = 0):0
using namespace std;
struct cell
{
int nodp,nodaj,val;
};
ifstream fin("pscnv.in");
ofstream fout("pscnv.out");
const int NMAX=250005;
const int MMAX=500005;
const int LIMIT=1005;
int n,m,x,y,f[NMAX],comp[NMAX],rad[NMAX],sum[LIMIT];
int pos;
cell que[MMAX];
char Buffer[Lim];
inline void Read(int &x)
{
bool ok=0;
while(Buffer[pos]<'0' || '9'<Buffer[pos])
{
if (Buffer[pos]=='-') ok=1;
Next;
}
x = 0;
while('0'<=Buffer[pos] && Buffer[pos]<='9')
{
x = x*10 +Buffer[pos]-'0';
Next;
}
if (ok==1) x=-x;
}
inline void Union(int x,int y)
{
if (comp[x]>comp[y])
{
f[y]=x;
comp[x]+=comp[y];
}
else
{
f[x]=y;
comp[y]+=comp[x];
}
}
inline int Father(int x)
{
int w,z;
z=x;
while (x!=f[x]) x=f[x];
while (z!=f[z])
{
w=f[z];
f[z]=x;
z=w;
}
return x;
}
int main()
{
int i,j,sol,ax,baux;
Read(n);Read(m);Read(x);Read(y);
for (i=1;i<=m;i++)
{
Read(que[i].nodp);Read(que[i].nodaj);Read(que[i].val);
sum[que[i].val]++;
}
for (i=1;i<LIMIT;i++) sum[i]+=sum[i-1];
for (i=m;i>=1;i--)
{
rad[sum[que[i].val]]=i;
sum[que[i].val]--;
}
for (i=1;i<=n;i++) {f[i]=i;comp[i]=1;}
for (j=1;j<=m;j++)
{
i=rad[j];
ax=Father(que[i].nodp);baux=Father(que[i].nodaj);
if (ax!=baux) Union(ax,baux);
ax=Father(x);baux=Father(y);
if (ax==baux) {sol=que[i].val;j=m+1;}
}
fout<<sol<<"\n";
return 0;
}