[UVa]10048:Audiophobia

這題是all-pairs shortest paths的問題，
我用Floyd-Warshall Algorithm解決掉XD

[C](0.028)

	#include<stdio.h>
	#define MAX_VALUE 2147483647
	int max( int a, int b )
	{
	return ( a > b )? a : b;
	}
	int min( int a, int b )
	{
	return ( a < b )? a : b;
	}
	int main()
	{
	int print = 0;
	int casenumber = 1;
	int C, S, Q;
	int point[105][105] = {0};
	while( scanf( "%d%d%d", &C, &S, &Q ) != EOF && C != 0 && S != 0 && Q != 0 )
	{
	if( print )
	printf( "\n" );
	print = 1;
	int i, j, k;
	for( i = 1 ; i <= C ; i++ )
	for( j = 1 ; j <= C ; j++ )
	{
	if( i != j )
	point[i][j] = MAX_VALUE;
	else
	point[i][j] = 0;
	}
	int point1, point2;
	for( i = 1 ; i <= S ; i++ )
	{
	scanf( "%d%d", &point1, &point2 );
	scanf( "%d", &point[point1][point2] );
	point[point2][point1] = point[point1][point2];
	}
	for( k = 1 ; k <= C ; k++ )
	for( i = 1 ; i <= C ; i++ )
	for( j = 1 ; j <= C ; j++ )
	{
	point[i][j] = min( point[i][j], max( point[i][k], point[k][j] ) );
	}
	printf( "Case #%d\n", casenumber );
	for( i = 1 ; i <= Q ; i++ )
	{
	scanf( "%d%d", &point1, &point2 );
	if( point[point1][point2] != MAX_VALUE )
	printf( "%d\n", point[point1][point2] );
	else
	printf( "no path\n" );
	}
	casenumber++;
	}
	return 0;
	}

view raw UVa10048.c hosted with ❤ by GitHub