[POJ] 2240 Arbitrage.cpp

#include <cstdio>
#include <string>
#include <map>
#include <queue>
using namespace std;
int main()
{
    int N, M, Case = 1;
    while (scanf("%d", &N) && N) {
        map<string, int> Map;
        double R[35][35] = {0};   // Rate

        // Initial
        for (int i = 0; i < N; ++i)
            R[i][i] = 1;

        // Input
        char a[100], b[100];
        double rate;
        for (int i = 0; i < N; ++i) {
            scanf("%s", a);
            Map[a] = i;
        }
        scanf("%d", &M);
        for (int i = 0; i < M; ++i) {
            scanf("%s %lf %s", a, &rate, b);
            R[Map[a]][Map[b]] = rate;
        }

        // Floyd
        for (int k = 0; k < N; ++k)
            for (int i = 0; i < N; ++i)
                for (int j = 0; j < N; ++j)
                    if (R[i][k]*R[k][j] > R[i][j])
                        R[i][j] = R[i][k]*R[k][j];

        // Analysis & Output
        bool Yes = false;
        for (int i = 0; i < N; ++i)
            if (R[i][i] > 1)
                Yes = true;
        printf("Case %d: ", Case++);
        if (Yes) puts("Yes");
        else puts("No");
    }
}