2570.txt

北大ACM题目例程 详细的解答过程 程序实现 算法分析

Problem Id:2570  User Id:fzk 
Memory:184K  Time:171MS
Language:C++  Result:Accepted

Source 

#include"stdio.h"

int e[201][201];

int main()
{
	int i,j,a,b,k,n;
	char w[100];
	
	while( 1 )
	{
		scanf( "%d", &n );
		if( n == 0 ) break;

		for( i=1; i<=n; i++ )
		for( j=1; j<=n; j++ )
			e[i][j] = 0;

		while( 1 )
		{
			scanf( "%d %d", &a, &b );
			if( a == 0 && b == 0 )break;
			scanf( "%s", w );

			for( i=0; w[i]; i++ )
				e[a][b] |= 1<< ( w[i]-'a' ) ;
		}

		for( k=1; k<=n; k++ )
		for( i=1; i<=n; i++ )
		for( j=1; j<=n; j++ )
			e[i][j] |= e[i][k] & e[k][j] ;

		while( 1 )
		{
			scanf( "%d %d", &a, &b );
			if( a == 0 && b == 0 )break;

			k = e[a][b];

			if( !k )printf( "-" );
			else for( i='a'; k ; i++,k>>=1 )
			{
				if( k & 1 ) printf( "%c", i );
			}
			printf( "\n" );
		}
		printf( "\n" );
	}
	return 0;
}