Pagini recente » Cod sursa (job #1861628) | Cod sursa (job #1653283) | Cod sursa (job #35757) | Cod sursa (job #3140277) | Cod sursa (job #328268)
Cod sursa(job #328268)
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#define in "pscnv.in"
#define out "pscnv.out"
#define NMAX 250055
#define MMAX 500055
struct muchie {
int v1, v2, cost;
} A[MMAX], aux;
int N, M, X, Y;
int tata[NMAX], rang[NMAX];
char buffer[10000000];
int Pivot ( int st, int dr )
{
int i,j;
i= rand()%(dr-st+1) + st;
aux = A[st];
A[st] = A[i];
A[i] = aux;
i = st - 1, j = dr + 1;
int pivot = A[st].cost;
while ( 1 )
{
do { j--; } while ( A[j].cost > pivot );
do { i++; } while ( A[i].cost < pivot );
if ( i < j )
{
aux = A[i];
A[i] = A[j];
A[j] = aux;
}
else return j;
}
}
void Quicksort ( int st, int dr )
{
int q;
if ( st < dr )
{
q = Pivot( st, dr );
Quicksort( st, q );
Quicksort ( q+1, dr );
}
}
int Find ( int x )
{
if ( x != tata[x] )
tata[x] = Find ( tata[x] );
return tata[x];
}
void Union ( int x, int y )
{
if ( rang[x] > rang[y] ) tata[y] = x;
else
{
tata[x] = y;
if ( rang[x] == rang[y] )
rang[y]++;
}
}
int main ( void )
{
freopen ( in, "r", stdin );
freopen ( out, "w", stdout );
scanf ( "%d %d %d %d\n", &N, &M, &X, &Y );
int last,ii,i,r1,r2,j,cost;
for ( i = 1; i <= N; ++i ) { tata[i] = i; rang[i] = 0; }
fread ( buffer, sizeof(char), 10000000, stdin );
char sep[] = " \n";
char *p;
p = strtok ( buffer, sep );
i = atoi ( p );
p = strtok ( 0, sep );
j = atoi ( p );
p = strtok ( 0, sep );
cost = atoi ( p );
A[1].v1 = i; A[1].v2 = j; A[1].cost = cost;
for ( ii = 2; ii <= M; ++ii )
{
p = strtok ( 0, sep );
i = atoi ( p ); A[ii].v1 = i;
p = strtok ( 0, sep );
j = atoi ( p ); A[ii].v2 = j;
p = strtok ( 0, sep );
cost = atoi ( p ); A[ii].cost = cost;
}
Quicksort ( 1, M );
for ( i = 1; i <= M; ++i )
{
r1 = Find( A[i].v1 );
r2 = Find ( A[i].v2 );
if ( r1 != r2 ) Union ( r1, r2 );
if ( Find(X) == Find( Y ) ) { last = A[i].cost; break; }
}
printf ( "%d\n", last );
return 0;
}