Pagini recente » Cod sursa (job #1598715) | Cod sursa (job #2031454) | Cod sursa (job #2452575) | Cod sursa (job #919218) | Cod sursa (job #952372)
Cod sursa(job #952372)
#include <iostream>
#include <fstream>
#include <vector>
#include <algorithm>
using namespace std;
//ifstream f("pscnv.in");
ofstream g("pscnv.out");
#define nmax 250005
#define Mmax 500005
#define Cifmax (1<<14)
int n, m, start, final, t[nmax];
vector< pair<int, pair<int,int> > > edge;
char S[Cifmax];
int poz;
void next(){
++poz; if (poz == Cifmax){
fread(S, 1, Cifmax, stdin);
poz = 0;
}
}
void buf(int &nr){
nr = 0;
for(; S[poz]<'0' || S[poz]>'9'; next());
for(; S[poz]>='0' && S[poz]<='9'; next()){
nr = nr * 10 + (S[poz] - '0');
}
}
void citeste(){
buf(n); buf(m); buf(start); buf(final);
int x, y, c;
for(int i=1; i<=m; ++i){
buf(x); buf(y); buf(c);
edge.push_back( make_pair( c, make_pair(x, y) ) );
}
}
inline int afla(int x){
int x2 = x;
for(; t[x] != 0; x = t[x]);
int temp = 0;
while(x2 != x){
temp = t[x2]; t[x2] = x; x2 = temp;
}
return x;
}
void uneste(int x, int y){
t[y] = x;
}
void rezolva(){
sort(edge.begin(), edge.end());
for(int i=0; i<m; ++i){
int radX = afla(edge[i].second.first);
int radY = afla(edge[i].second.second);
if (radX == radY) continue;
uneste(radX, radY); // x -> y;
if ( afla(start) == afla(final) ) {
g << edge[i].first << "\n";
return;
}
}
}
int main(){
freopen("pscnv.in", "r", stdin);
citeste();
rezolva();
fclose(stdin);
g.close();
return 0;
}