Hdu-177 Abrange

テーマリンク:http://acm.hdu.edu.cn/showproblem.php?pid=1217
タイトルの大意:
N種の通貨をあげて、二つの通貨の間の為替レートをあげます.1単位の通貨が複数回両替した後、1単位より大きい場合、Yesを出力します.そうでなければNo.
問題解決の考え方:
1.mapの簡単なアプリケーション
2.Floydアルゴリズムの変形は、その後dis[i][i]を判断し、1より大きいと存在する.
コードは以下の通りです

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

#define N 35
int num, road;
double dis[N][N]; //    。。。。      

bool Floyd()
{
    bool flag;
    for(int k = 1; k <= num; ++k) //Floyd
        for(int i = 1; i <= num; ++i) 
            for(int j = 1; j <= num; ++j) //    
                if(dis[i][j] < dis[i][k] * dis[k][j])
                    dis[i][j] = dis[i][k] * dis[k][j];
    flag = false;
    for(int i = 1; i <= num; ++i) //       1
        if(dis[i][i] > 1)
        {
            flag = true;
            break;
        }
        return flag;
}

int main()
{
    int ncase = 1;
    char money[35], b[35], e[35];
    double cost;
    map<string, int> mp;
    while(scanf("%d", &num) && num)
    {
        mp.clear();
        memset(dis, 0, sizeof(dis));
        for(int i = 1; i <= num; ++i)
        {
            scanf("%s", money);
            mp[money] = i;
        }
        scanf("%d", &road);
        for(int i = 1; i <= road; ++i)
        {
            scanf("%s%lf%s", b, &cost, e);
            dis[mp[b]][mp[e]] = cost;
        }
        printf("Case %d: ", ncase++);
        if(Floyd()) printf("Yes
");
        else printf("No
");
    }
    return 0;
}