POJ 2240 Arbitrage

Description

存在多种货币，给出它们兑换时的汇率，问是否存在一种货币，经过多次兑换，最终换回自己时钱多了……

The link of the problem http://poj.org/problem?id=2240

最短路变形

广义最短路: 存在多个状态，从此状态到彼状态的最优过渡方案

另外，用map从string映射到int

Code of Floyd

#include <map>
#include <cstdio>
#include <string>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;

///最短路:存在多个状态，从此状态到彼状态的最优过渡方案
int n, m, num = 1;
double dis[44][44];


void floyd()
{
    for(int k = 0; k < n; ++k)
        for(int i = 0; i < n; ++i)
            for(int j = 0; j < n; ++j)///距离用+汇率用*
                if(dis[i][j] < dis[i][k] * dis[k][j])
                    dis[i][j] = dis[i][k] * dis[k][j];
}

int main()
{
    while(~scanf("%d", &n) && n)
    {
        map<string, int> mp;
        string s;
        for(int i = 0; i < n; ++i)
        {
            cin >> s;
            mp[s] = i;
        }
        memset(dis, 0, sizeof(dis));///初始化为0表示两货币无法兑换
        for(int i = 0; i < n; ++i)
            dis[i][i] = 1;///自身换自身 1: 1
        scanf("%d", &m);
        string a, b;
        double tra;
        for(int i = 0; i < m; ++i)
        {
            cin >> a >> tra >> b;
            dis[ mp[a] ][ mp[b] ] = tra;///单向路
        }
        floyd();
        bool flag = 0;
        for(int i = 0; i < n; ++i)
        {
            if(dis[i][i] > 1)
            {
                flag = 1;
                break;
            }
        }
        if(flag)
            printf("Case %d: Yes\n", num++);
        else
            printf("Case %d: No\n", num++);
    }
}