Pagini recente » Cod sursa (job #1030244) | Cod sursa (job #635939) | Cod sursa (job #1344100) | Cod sursa (job #2712972) | Cod sursa (job #930648)
Cod sursa(job #930648)
#include<cstdio>
#include<list>
#define pb push_back
#define mkp make_pair
#define pii pair<int, int>
#define ll long long
#define FOR(i,a,b)\
for(int i=a; i<=b; ++i)
#define ALL(g)\
for(typeof(g.begin()) it=g.begin(); it!=g.end(); ++it)
#define infile "pscnv.in"
#define outfile "pscnv.out"
#define nMax 250005
#define kMax 1005
using namespace std;
list < pair < int, int > > L[kMax];
int T[nMax], R[nMax];
int Cmax, Sol;
int N, M, X, Y;
void read(){
freopen(infile, "r", stdin);
scanf("%d %d %d %d\n", &N, &M, &X, &Y);
int x, y, cost;
FOR(i,1,M){
scanf("%d %d %d", &x, &y, &cost);
L[cost].pb(mkp(x,y));
Cmax = max(Cmax, cost);
}
fclose(stdin);
}
inline int Find(int x){
int r, y;
for(r = x; T[r] != r; r = T[r]);
while(T[x] != x){
y = T[x];
T[x] = r;
x = y;
}
return r;
}
inline void Union(int x, int y){
if(R[x] < R[y])
T[x] = y;
else
T[y] = x;
if(R[x] == R[y])
R[x] ++;
}
void solve(){
FOR(i,1,N)
T[i] = i, R[i] = 1;
while(Sol < Cmax && Find(X) != Find(Y)){
Sol ++;
ALL(L[Sol])
Union(Find((*it).first), Find((*it).second));
}
}
void print(){
freopen(outfile, "w", stdout);
printf("%d\n", Sol);
fclose(stdout);
}
int main(){
read();
solve();
print();
return 0;
}