Follows 117.c (Total 73 lines):

/* @JUDGE_ID:4461XX 117 C */
/* A */
#include<stdio.h>
#include<string.h>
int map[26][26] , degree[26] , oddpoint[2] ;
void init( void )
{
	int i , j ;
	for( i=0 ; i<26 ; i++ )
	for( j=0 ; j<26 ; j++ ) map[i][j] = 0 ;
		for( i=0 ; i<26 ; i++ ) degree[i] = 0 ;
}
void make_map( int len , char star , char end )
{
	map[star-'a'][end-'a'] = map[end-'a'][star-'a'] = len ;
	degree[star-'a']++ ;
	degree[end-'a']++ ;
}
int all_even( void )
{
	int i , j , alleven ;
	for( alleven=1 , j=i=0 ; i<26 ; i++ )
		if( degree[i]%2 ){
			alleven = 0 ;
			oddpoint[j++] = i ;
		}
	if( alleven ) return 1 ;
	else return 0 ;
}
int add( void )
{
	int i , j , step=0 ;
	for( i=0 ; i<26 ; i++ )
		for( j=0 ; j<26 ; j++ ) step += map[i][j] ;
	step /= 2 ;
	return step ;
}
int Min( int a , int b )
{
	if( !b ) return a ;
	if( a<b ) return a ;
	else return b ;
}
void warshall( void )
{
	int i , j , k ;
	for( k=0 ; k<26 ; k++ )
		for( i=0 ; i<26 ; i++ )
			for( j=0 ; j<26 ; j++ )
				if( map[i][k] && map[k][j] )
					map[i][j] = Min( map[i][k]+map[k][j] , map[i][j] ) ;
}
void main( void )
{
	char str[100] ;
	int step ;
/* freopen( "C:\\windows\\desktop\\117.in" , "r" , stdin ) ; */
	while( gets( str ) ){
		init() ;
		make_map( strlen( str ) , *str , *(str+strlen(str)-1) ) ;
		for( ; ; ){
			gets( str ) ;
			if( !strcmp( str , "deadend" ) ) break ;
			make_map( strlen( str ) , *str , *(str+strlen(str)-1) ) ;
		}
		step = add() ;
		if( !all_even() ){
			warshall() ;
			step += map[oddpoint[0]][oddpoint[1]] ;
		}
		printf( "%d\n" , step ) ;
	}
}

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