Pagini recente » Cod sursa (job #3030216) | Cod sursa (job #3255694) | Cod sursa (job #726514) | Cod sursa (job #3283041) | Cod sursa (job #951068)
Cod sursa(job #951068)
#include <cstdio>
#include <algorithm>
#include <vector>
#include <queue>
#define dim 8192
using namespace std;
const char iname[] = "pscnv.in";
const char oname[] = "pscnv.out";
struct muchie{int x, y, cost; muchie(){}; muchie(int X, int Y, int Z){x = X; y = Y; cost = Z;};}Arc;
vector <muchie> v;
vector <muchie> :: iterator it, fin;
int x;
char ax[dim];
int pz;
inline void cit(int &x){
x = 0;
while (ax[pz] < '0' || ax[pz] > '9')
if (++pz == dim)
fread (ax, 1, dim, stdin), pz = 0;
while (ax[pz] >= '0' && ax[pz] <= '9'){
x = x * 10 + ax[pz] - '0';
if (++pz == dim)
fread (ax, 1, dim, stdin), pz = 0;
}
}
struct cmp{
bool operator()(const muchie &A, const muchie &B) const
{
if (A.cost < B.cost) return 1;
return 0;
};
};
int N, M, A, B, i, ANS;
int t[250004];
inline int find(int i)
{
if (t[i] != i) t[i] = find(t[i]);
return t[i];
}
inline int uneste(int i, int j)
{
i = find(i); j = find(j);
if (i == j) return 0;
t[i] = j;
return 1;
}
int main(){
freopen(iname,"r",stdin);
freopen(oname,"w",stdout);
cit(N); cit(M); cit(A); cit(B);
for (i = 1; i <= N; ++i) t[i] = i;
while (M--){
cit(Arc.x); cit(Arc.y); cit(Arc.cost);
v.push_back(Arc);
}
sort (v.begin(), v.end(), cmp());
it = v.begin(), fin = v.end();
while (find(A) != find(B) && it != fin){
Arc = *it;
if (find(Arc.x) != find(Arc.y)){
uneste(Arc.x, Arc.y);
ANS = max(ANS, Arc.cost);
}
++it;
}
printf("%d\n", ANS);
return 0;
}