Floyd算法

#include <stdio.h>
#include <string.h>

double d[31][31], r;
char cur[31][50], src[50], dest[50];
int n, m;

int find(char *str)
{
    int i;

    for(i = 0; i < n; i++)
        if(!strcmp(str, cur[i]))
            return i;
}

void floyd(void)
{
    int u, v, w;

    for(u = 0; u < n; u++)
        for(v = 0; v < n; v++)
            for(w = 0; w < n; w++)
            {
                if(d[v][w] < d[v][u] * d[u][w])
                    d[v][w] = d[v][u] * d[u][w];
            }
}

int main(void)
{
    int i, j, sr, dt, flag, sum;

    sum = 0;
    while(scanf("%d", &n) != EOF && n)
    {
        sum++;
        for(i = 0; i < n; i++)
            for(j = 0; j < n; j++)
                d[i][j] = 0;

        for(i = 0; i < n; i++)
            scanf("%s", cur[i]);

        flag = 0;
        scanf("%d", &m);
        for(i = 0; i < m; i++)
        {
            scanf("%s%lf%s", src, &r, dest);
            sr = find(src);
            dt = find(dest);

            if(d[sr][dt] < r)
                d[sr][dt] = r;

            /*if adding value after transforming itself, then no need to floyd. */
            if(!flag && (sr == dt) && (r > 1))
                flag = 1;
        }

        if(flag)
            printf("Case %d: Yes\n", sum);
        else
        {
            floyd();

            for(i = 0; i < n; i++)
            {
                if(d[i][i] > 1)
                {
                    printf("Case %d: Yes\n", sum);
                    break;
                }
            }

            if(i == n)
                printf("Case %d: No\n", sum);
        }
    }

    return 0;
}