HDU1869最短路径,弗洛伊德算法

文章目录

 #include <stdio.h>
 #include<math.h>
 #include<stdlib.h>
 //这个数不能太大也不能太小，太大了两个数相加时就越界了，刚开始是2<<29;结果WA了
 #define max 2<<10 
int map[105][105];
int d[105][105];
int main(int argc, char *argv[])
{
 int n,i,j,k,t,m;
 int a,b;
 while(scanf("%d%d",&n,&m)!=EOF){
  for(i=0;i<105;i++)//初始化。。
  for(j=0;j<105;j++)
 map[i][j]=max;
  for(i=0;i<m;i++){
   scanf("%d%d",&a,&b);
   if(a==b)
   map[a][b]=map[b][a]=0;
   else map[a][b]=map[b][a]=1;
  }
  for(i=0;i<n;i++)//初始化。。。
  for(j=0;j<n;j++)
  if(i==j) d[i][j]=0;
  else d[i][j]=d[j][i]=map[i][j];
  for(k=0;k<n;k++)//弗洛伊的算法。。不要搞乱顺序哦。。。
  for(i=0;i<n;i++)
  for(j=0;j<n;j++)
  if(d[i][j]>d[i][k]+d[k][j])
  d[i][j]=d[i][k]+d[k][j];
  int flag=0;
  for(i=0;i<n;i++){
  for(j=0;j<n;j++)
  if(d[i][j]>7){//题意说最多只隔着6个人，对应七条边。。。
   flag=1;
   break;
  }
  }
  if(flag==1)
  printf("No\n");
  else printf("Yes\n");
 }
 return 0;
}