PersonalCorpus 版 (精华区)

1259808 Big Guava ... 436 Accepted
0:00.061 64 2002/11/24 10:27:12.673

int main()
{
#ifndef ONLINE_JUDGE
    freopen("c:\\0acm\\zju\\i1092","r",stdin);
    freopen("c:\\0acm\\zju\\o1092","w",stdout);
#endif
    char name[30][260],s[260],ss[260],path[3000];
    int i,j,k,n,m,t=0;
    double dl[30][30],tmp,v[30];
    bool ok;
    while (1) {
        scanf("%d\n",&n);
        if (n==0) break; else t++;
        for (i=0;i<n;i++) gets(name[i]);
        scanf("%d\n",&m);
        for (i=0;i<n;i++) for (j=0;j<n;j++) dl[i][j]=0;
        for (i=0;i<m;i++) {
            scanf("%s %lf %s\n",s,&tmp,ss);
            for (j=0;j<n;j++) if (strcmp(name[j],s)==0) break;
            for (k=0;k<n;k++) if (strcmp(name[k],ss)==0) break;
            if (tmp>dl[j][k]) dl[j][k]=tmp;
        }
        ok=false;
        for (m=0;m<n;m++) {
            for (j=0;j<n;j++) v[j]=0;
            v[m]=1000; path[0]=m;
            i=0;j=1;
            while (i<j) {
                for (k=0;k<n;k++) if (dl[path[i]][k]>0) {
                    tmp=v[path[i]]*dl[path[i]][k];
                    if ((v[k]==0)||(tmp>v[k])) {
                        if (k==m) {
                            ok=true;
                            i=j;
                            break;
                        }
                        v[k]=tmp;
                        path[j++]=k;
                    }
                }
                if (!ok) i++;
            }
            if (ok) break;
        }
        if (ok) printf("Case %d: Yes\n",t);
        else printf("Case %d: No\n",t);
    }
}