hdu 1869

1つの最短経路の変形、問題を解決する構想も広くて柔軟で、実はすべて万変してその宗から離れません
 
 
 
ろくどぶんり
Time Limit: 5000/1000 MS (Java/Others)    Memory Limit: 32768/32768 K (Java/Others)Total Submission(s): 726    Accepted Submission(s): 275
Problem Description
1967年、米国の著名な社会学者スタンリー・ミルグランムは「小世界現象(small world phenomenon)」という有名な仮説を提出した.(six degrees of separation).ミルグラムの理論はしばしば当てはまり、多くの社会学者が興味を持っていたが、30年以上も厳密な証明を得たことがなく、伝奇的な仮説にすぎなかった.
Leleはこの理論にかなり興味を持っていたので、HDUでN人に対して調査を行いました.彼はすでに彼らの間の知り合い関係を得ています.今、「六度分離」が成立したかどうかを検証してください.
 
 
Input
この問題には複数のテストが含まれています.ファイルが終わるまで処理してください.
各組の試験について、第1行は2つの整数N、M(0は次にM行、各行は2つの整数A、B(0<=A、BはこのM組の関係を除いて、他の任意の2人の間では知られていない.
 
 
Output
各グループのテストについて、データが「6度分離」理論に合致する場合は、1行に「Yes」を出力し、そうでない場合は「No」を出力します.
 
 
Sample Input
8 7 0 1 1 2 2 3 3 4 4 5 5 6 6 7 8 8 0 1 1 2 2 3 3 4 4 5 5 6 6 7 7 0
 
 
Sample Output
Yes Yes
 
My Solution:
//六度の分離、中間ノードの数を求めて、実は任意の2点の間の距離に転化することができて、(跳数)直接変化する接続距離は1で、距離が無限大ではありません
#include
#define MAX 100000000
using namespace std;
int map[100][100];
void floyed(int n)
{
 for(int k=0;k  for(int i=0;i   for(int j=0;j    if(map[i][k]+map[k][j]}
bool judge(int n)
{
 for(int i=0;i  for(int j=0;j   if(map[i][j]>7)return false;
 return true;
}
int main()
{
 int n,m;
 int i,j;
 while(cin>>n>>m)
 {
  for(i=0;i   for(j=i+1;j    map[i][j]=map[j][i]=MAX;
   for(i=0;i  int v1,v2;
  for(i=0;i  {
   cin>>v1>>v2;
   map[v1][v2]=map[v2][v1]=1;
  }
  floyed(n);
  if(judge(n))cout<  else cout< }
 return 0;
}