hdu1217 floyd

floyd一遍即可。如果floyd后值有变大就是

#include<map>
#include<string>
#include<stdio.h>
#include<string.h>
#include<iostream>
#define INF 99999999
using namespace std;
const int maxn=36;
double mmap[maxn][maxn],val;
int n;
void init()
{
    int i,j;
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
            mmap[i][j]=0;
}
void floyd()
{
    int i,j,k;
    for(k=1;k<=n;k++)
        for(i=1;i<=n;i++)
            for(j=1;j<=n;j++)
            {
                if(mmap[i][j]<mmap[i][k]*mmap[k][j])
                    mmap[i][j]=mmap[i][k]*mmap[k][j];
            }
}
int main()
{
    int i,j,m,ff=0;
    string s;
    while(scanf("%d",&n)!=EOF)
    {
        if(!n)break;
        init();
        int count=0;
        map<string,int>Map;
        for(i=0;i<n;i++)
        {
            cin>>s;
            Map[s]=++count;
        }
        scanf("%d",&m);
        string s1,s2;
        for(i=0;i<m;i++)
        {
            cin>>s1;
            scanf("%lf",&val);
            cin>>s2;
            if(mmap[Map[s1]][Map[s2]]<val)
                mmap[Map[s1]][Map[s2]]=val;
        }
        floyd();
        int flag=0;
        for(i=1;i<=n;i++)
            if(mmap[i][i]>1)
            {
                flag=1;
                break;
            }
        if(flag)
        {
            printf("Case %d: Yes
",++ff);
        }
        else printf("Case %d: No
",++ff);
    }
}