Pagini recente » Cod sursa (job #2633600) | Cod sursa (job #709773) | Cod sursa (job #1053817) | Cod sursa (job #2172878) | Cod sursa (job #1013278)
#include <algorithm>
#include <cstdio>
#include <vector>
#include <queue>
void scan(int &A)
{
char c = 0;A = 0;
do
{
c = fgetc(stdin);
if('0'<=c && c<='9')
A = A * 10 + c - 48;
}while('0'<= c && c<='9');
}
using namespace std;
const int INF = 0x3f3f3f3f;
const int Nmax = 250005;
struct arce{
int x;
int y;
int cost;
};
int N,M,fr,to; // from , to
int D[Nmax],daddy[Nmax];
vector<pair<int,int> > G[Nmax];
struct cmp{
bool operator()(const arce A,const arce B)const
{
return A.cost > B.cost;
}
};
priority_queue<arce,vector<arce>,cmp> Q;
inline int whos_ur_daddy(int nodc)
{
if(daddy[nodc]!= nodc)
daddy[nodc]=whos_ur_daddy(daddy[nodc]);
return daddy[nodc];
}
inline void couple(int a,int b){daddy[daddy[a]] = daddy[b];}
void getg()
{
scan(N),scan(M),scan(fr),scan(to);
for(int i = 1; i <= N; ++i)daddy[i] = i;
arce A;
for(int i = 1; i <= M; ++i)
{
scan(A.x),scan(A.y),scan(A.cost);
Q.push(A);
}
}
void kruskal()
{
int step = 0;
arce A;
while( step != N - 1)
{
A = Q.top();Q.pop();
if(whos_ur_daddy(A.x)!=whos_ur_daddy(A.y))
{
couple(A.x,A.y);
++step;
G[A.x].push_back(make_pair(A.y,A.cost));
}
}
}
void DFS(int nodc)
{
vector<pair<int,int> >::iterator it;
for(it = G[nodc].begin() ; it != G[nodc].end();++it)
if(!D[it->first])
{
D[it->first] = max(D[nodc],it->second);
DFS(it->first);
}
}
void solve()
{
kruskal();
DFS(fr);
printf("%d",D[to]);
}
int main()
{
freopen("pscnv.in","r",stdin);
freopen("pscnv.out","w",stdout);
getg();
solve();
return 0;
}