Cod sursa(job #328268)

Utilizator TabaraTabara Mihai Tabara Data 1 iulie 2009 14:19:26
Problema PScNv Scor 100
Compilator c Status done
Runda Arhiva de probleme Marime 1.9 kb
#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;
}