HDU 1869 六度分离 (floyd)

http://acm.hdu.edu.cn/showproblem.php?pid=1869

这题是简单的弗洛伊德算法的转变，在最后判定的时候是跟7进行判定，因为点与点间的路径是没用算上本身那个cost的

#include<stdio.h>
#include<string.h>
#define MAX 9999999
int map[1000][1000];
int vertex,edge;
void init()
{
    int i,j;
    for(i=0;i<vertex;i++)
        for(j=0;j<vertex;j++)
        if(i==j)map[i][j]=0;
        else map[i][j]=MAX;//起点跟终点一致，说明可以0费用，否则就先初始化为最大
}
int floyd()
{
    int i,j,k,sum;
    for(k=0;k<vertex;++k)
        for(i=0;i<vertex;++i)
            for(j=0;j<vertex;++j)
            {
                sum=map[i][k]+map[k][j];
                if(sum<map[i][j])
                {
                    map[i][j]=sum;//如果存在k点使得ij路径可松弛，那么就更新这条路径上的数据
                }
            }
    for(i=0;i<vertex;++i)
        for(j=0;j<vertex;++j)
        {
            if(map[i][j]>7)return 0;
        }
    return 1;
}

int main()
{
    int i,j,x,y;
    while(scanf("%d%d",&vertex,&edge)!=EOF)
    {
        init();
        for(i=0;i<edge;i++)
        {
            scanf("%d%d",&x,&y);
            map[x][y]=map[y][x]=1;
        }
        printf("%s
",floyd()?"Yes":"No");
    }
    return 0;
}