Pagini recente » Cod sursa (job #708443) | Cod sursa (job #1598160) | abcd1234 | Cod sursa (job #439584) | Cod sursa (job #952367)
Cod sursa(job #952367)
#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
int n, m, start, final, t[nmax];
vector< pair<int, pair<int,int> > > edge;
void citeste(){
f >> n >> m >> start >> final;
int x, y, c;
for(int i=1; i<=m; ++i){
f >> x >> y >> 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";
//cout << edge[i].first << "\n";
return;
}
}
}
int main(){
citeste();
rezolva();
f.close();
g.close();
return 0;
}