pku 2240 Arbitrage第1週トレーニング——最短ルート

http://poj.org/problem?id=2240
最初にタイトルを見たとき、データ量が小さいのを見て、検索を考えて、すべてのループを検索して、エッジの重み値を乗じて1.0のループに大きいかどうかを見ました.結果は果敢なTLEで無言...
最後にDiscuss floyd 1 Aを見て


View Code

#include <iostream>
#include <cstring>
#include <cstdio>
#include <cmath>
#define maxn 34
#define eps 1e-8
using namespace std;
char str[maxn][maxn];
double map[maxn][maxn];
bool vt[maxn];
int ans,tmp;
int n,m;
void init()
{
    int i,j;
    for (i = 0; i <= n; ++i)
    {
        for (j = 0; j <= n; ++j)
        {

            map[i][j] = 0;//    0，        
        }
    }
}
void floyd()
{
    int i,j,k;
    for (k = 0; k < n; ++k)
    {
        for (i = 0; i < n; ++i)
        {
            for (j = 0; j < n; ++j)
            {
                if (map[i][k]*map[k][j] - map[i][j] > eps )//      i!=j    ，           
                map[i][j] = map[i][k]*map[k][j];
            }
        }
    }
}
int getpos(char *t)
{
    for (int i = 0; i < n; ++i)
    {
       if (strcmp(t,str[i]) == 0)
       return i;
    }
    return -1;
}
int main()
{
    int i,cas = 1;
    char s1[maxn],s2[maxn];
    double val;
    while (~scanf("%d",&n))
    {
        if (!n) break;
        init();
        for (i = 0; i < n; ++i)
        scanf("%s",str[i]);
        scanf("%d",&m);
        for (i = 0; i < m; ++i)
        {
            scanf("%s%lf%s",s1,&val,s2);
            int pos1 = getpos(s1);
            int pos2 = getpos(s2);
            //printf("%d %d
",pos1,pos2);
            map[pos1][pos2] = val;
        }
        floyd();
        /*for (i =0; i < n; ++i)
        {
            printf(">>>%.2lf
",map[i][i]);
        }*/
        bool flag = false;
        for (i = 0; i < n; ++i)
        {
            if (map[i][i] > 1.0)
            {
                flag = true;
                break;
            }
        }
        if (flag) printf("Case %d: Yes
",cas++);
        else      printf("Case %d: No
",cas++);
    }
    return 0;
}