poj 2240 Arbitrage

Arbitrage

题目链接：http://poj.org/PRoblem?id=2240

题目大意：几种货币之间汇率换算，问是否存在一种情况使得兑换了一圈回来，能盈利，也就是大于 1。

本题与 poj3259 极为相似，只不过本题目为乘，那个为加。

详见代码注释：

#include <iostream>  #include <cstdio>#include<cstring>using namespace std;  const double INF=0x3f3f3f3f; double dis[35][35];int n,m;char a[35][50];int f(char x[]){	for(int i=1;i<=n;i++)		if(strcmp(x,a[i])==0)			return i;} int main() {	int index=0;	int flag;    char x[50],y[50];    double d;    int a1,b1;    while(scanf("%d",&n),n)    {    	flag=0;    	for(int i=1;i<=n;i++)		{			for(int j=1;j<=n;j++)			{				dis[i][j]=0;	//³õʼ»¯ ÎÞÇî ¸ÄΪÁË 0 			}		}		for(int i=1;i<=n;i++)		{			dis[i][i]=1;	//¶Ô½ÇÏ߸³³õÖµ 1 		}							    	for(int i=1;i<=n;i++)    	{    		scanf("%s",a[i]);		}		cin>>m;		for(int i=0;i<m;i++)		{			scanf("%s %lf %s",x,&d,y);			a1=f(x);b1=f(y);			dis[a1][b1]=d;		}        for (int k=1;k<=n;k++)            for (int i=1;i<=n;i++)                  for (int j=1;j<=n;j++)                    if (dis[i][j]<dis[i][k]*dis[k][j])	//Ô­ÏȵļӱäΪÁË³Ë                     	dis[i][j]=dis[i][k]*dis[k][j];                    		for(int i=1;i<=n;i++)	        if(dis[i][i]>1.0)	    	{	           	flag=1;	          	break;			}		if(flag)			printf("Case %d: Yes/n",++index);		else			printf("Case %d: No/n",++index);    }      return 0;  }