Follows 383.c (Total 80 lines):

/* @JUDGE_ID:4461XX 383 C "warshall" */
/* A */
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#define MAX 30

char city[MAX][2+1] ;
int map[MAX][MAX] , n ;

int find_city( char *name )
{
	int i ;

	for( i=0 ; i<n ; ++i )
		if( !strcmp( name , city[i] ) ) return i ;

	return -1 ;
}
void Warshall( void )
{
	int i , j , k ;

	for( k=0 ; k<n ; ++k )
		for( i=0 ; i<n ; ++i )
			for( j=0 ; j<n ; ++j )
				if( i!=j&&map[i][k]&&map[k][j] )
					if( !map[i][j] || map[i][k]+map[k][j]<map[i][j] )
						map[i][j] = map[i][k]+map[k][j] ;
}
void Input( void )
{
	char in[100] , tmp[2+1] , *p ;
	int i , m , k , c1 , c2 , wei ;

	scanf( "%d %d %d\n" , &n , &m , &k ) ;
	memset( map , 0 , sizeof( int )*MAX*MAX ) ;

	for( i=0 ; i<n ; ++i ) scanf( "%s" , city[i] ) ;
	for( i=0 ; i<m ; ++i ){
		scanf( "%s" , tmp ) ;
		c1 = find_city( tmp ) ;
		scanf( "%s" , tmp ) ;
		c2 = find_city( tmp ) ;

		map[c1][c2] = map[c2][c1] = 1 ;
	}

	Warshall() ;

	for( i=0,scanf( "\n" ) ; i<k ; ++i ){
		gets( in ) ;

		p = strtok( in , " " ) ;
		wei = atoi( p ) ;
		p = strtok( NULL , " " ) ;
		c1 = find_city( p ) ;
		p = strtok( NULL , " " ) ;
		c2 = find_city( p ) ;
		
		if( map[c1][c2] ) printf( "$%d00\n" , wei*map[c1][c2] ) ;
		else puts( "NO SHIPMENT POSSIBLE" ) ;
	}
}
int main( void )
{
	int case_time , i ;

	scanf( "%d" , &case_time ) ;
	puts( "SHIPPING ROUTES OUTPUT" ) ;
	
	for( i=1 ; i<=case_time ; ++i ){
		printf( "\nDATA SET  %d\n\n" , i ) ;
		Input() ;
	}
	
	puts( "\nEND OF OUTPUT" ) ;

	return 0 ;
}

Back to statistics
Ya-Lin Huang (C)
huangyl@gmail.com