http://poj.org/problem?id=2240
题意：有些人会利用货币的不用汇率来进行*，比如1美元换0.5英镑，而1英镑又可以换10法郎，而1法郎又可以换0.21的美元，那么经过货币的汇率转换后，它就可以获得1.05倍原来的美元。
现在给你N中货币，m种货币的汇率，求是否可以获利。
思路：首先这个是给你一些货币，那么我们可以把货币和数字建立一个映射。然后再用他给的汇率以及数字建立一个邻接矩阵。用一次floyd后对对角线的数字进行判断，如果大于1，那么说明可以获利，不然就不能获利。
这个题我用c++是78ms，用G++是700多ms。
#include <stdio.h>
#include <string.h>
#include <map>
#include <string>
#include <iostream> using namespace std; map< string , int > s; double graph[ ][ ]; int main()
{
// freopen("in.txt","r",stdin);
int n,p = ;
while( cin>>n,n )
{
p++;
memset( graph , , sizeof( graph ) );
string a , b;
double m;
int x,mark = ;
for(int i = ; i <= n ; i++ )
{
cin>>a;
s[ a ] = i; //对货币和数字建立一个映射。
}
cin>>x;
for( int i = ; i <= x ; i++ )
{
cin>>a>>m>>b;
graph[ s[ a ] ][ s[ b ] ] = m;
}
for( int k = ; k <= n ; k++ ) //floyd求出两个货币间的最大汇率。
for( int i = ; i <= n ; i++ )
for( int j = ; j <= n ; j++ )
if( graph[ i ][ j ] < graph [ i ][ k ]*graph[ k ][ j ])
graph[ i ][ j ] = graph [ i ][ k ]*graph[ k ][ j ];
for(int i = ; i <= n ; i++ ) //判断。
if( graph[ i ][ i ] > ) mark = ;
if( mark ) printf("Case %d: Yes\n",p);
else printf("Case %d: No\n",p);
}
return ;
}