POJ 2240 Arbitrage(最短路 套汇)

题意  给你n种币种之间的汇率关系  推断是否能形成套汇现象  即某币种多次换为其他币种再换回来结果比原来多

基础的最短路  仅仅是加号换为了乘号

#include<cstdio>
#include<cstring>
#include<string>
#include<map>
using namespace std;
map<string, int> na;
const int N = 31;
double d[N], rate[N][N], r;
int n, m, ans;

int bellman(int s)
{
    memset(d, 0, sizeof(d));
    d[s] = 1.0;
    for(int k = 1; k <= n; ++k)
    {
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 1; j <= n; ++j)
                if(d[i] < d[j]*rate[j][i])
                    d[i] = d[j] * rate[j][i];
        }
    }
    return d[s] > 1.0;
}

int main()
{
    int cas = 0;
    char s[100], a[100], b[100];
    while(scanf("%d", &n), n)
    {
        na.clear();
        ans = 0;
        memset(rate, 0, sizeof(rate));
        for(int i = 1; i <= n; ++i)
        {
            rate[i][i] = 1.0;
            scanf("%s", s);
            na[s] = i;
        }

        scanf("%d", &m);
        for(int i = 1; i <= m; ++i)
        {
            scanf("%s%lf%s", a, &r, b);
            rate[na[a]][na[b]] = r;
        }

        for(int i = 1; i <= n; ++i)
        {
            if(bellman(i))
            {
                ans = 1; break;
            }
        }
        printf("Case %d: %s\n", ++cas, ans ? "Yes" : "No");
    }
    return 0;
}

Description

Input

Output

Sample Input

3
USDollar
BritishPound
FrenchFranc
3
USDollar 0.5 BritishPound
BritishPound 10.0 FrenchFranc
FrenchFranc 0.21 USDollar

3
USDollar
BritishPound
FrenchFranc
6
USDollar 0.5 BritishPound
USDollar 4.9 FrenchFranc
BritishPound 10.0 FrenchFranc
BritishPound 1.99 USDollar
FrenchFranc 0.09 BritishPound
FrenchFranc 0.19 USDollar

0

Sample Output

Case 1: Yes
Case 2: No