学步园

最短路 floyed 判环：

理解floyed的核心为3个for循环：

还有此题就是对于名字的处理。

用了name二维数组，而用map类的话会非常的方便。

核心：

map<string,ing>name;

name[str]=i;

附上代码：

#include<stdio.h>
#include<string.h>
char name[32][100];
double map[32][32];
double divs[32];
int vis[32];
char s1[100];
char s2[100];

int n;
int get(char s[])
{
    for(int i=0; i<n; i++)
        if(!strcmp(s,name[i]))
            return i;
}
void floyed()
{
    for(int k=0; k<n; k++)
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(map[i][j]<map[i][k]*map[k][j])
                    map[i][j]=map[i][k]*map[k][j];
}
int main()
{
    int cnt=0;
    while(~scanf("%d",&n),n)
    {
        getchar();
        memset(vis,0,sizeof(vis));
        for(int i=0; i<n; i++)
            for(int j=0; j<n; j++)
                if(i==j)
                    map[i][j]=1;
                else
                    map[i][j]=0;
        for(int i=0; i<n; i++)
            gets(name[i]);
        int t;
        scanf("%d",&t);
        for(int i=0; i<t; i++)
        {
            double c;
            scanf("%s%lf%*c%s",s1,&c,s2);
            int a=get(s1);
            int b=get(s2);
            //printf("**%d  %d\n",a,b);
            if(map[a][b]<c)
                map[a][b]=c;
        }
        floyed();
        int flag=0;
        for(int i=0; i<n; i++)
            if(map[i][i]>1)
            {
                flag=1;break;
            }
        printf("Case %d: %s\n",++cnt,flag==1?"Yes":"No");
    }
    return 0;
}