首页 > 代码库 > HDU-1869-六度分离
HDU-1869-六度分离
题目链接
http://acm.hdu.edu.cn/showproblem.php?pid=1869
分析:这题可以用最短路来做,把认识的两个人看做相距为1的两个点,而不认识的两个人,看做相距为无穷大的两个点,就可以用最短路来做了,对于点数小于100用Floyd算法就可以了,这个题用Dijkstra,应该可以,
代码
#include<stdio.h>
#include<string.h>
const int M=999999999;
int main(void)
{
int n,m,visit[111][111];
int i,j,k,l;
int a,b;
while(scanf("%d%d",&n,&m)==2)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(i==j)
visit[i][j]=visit[j][i]=0;
else
visit[i][j]=visit[j][i]=M;
}
}
for(i=0;i<m;i++)
{
scanf("%d%d",&a,&b);
visit[a][b]=visit[b][a]=1;
}
for(k=0;k<n;k++)
{
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(visit[i][k]+visit[k][j]<visit[i][j])
visit[i][j]=visit[i][k]+visit[k][j];
}
}
}
for(i=0;i<n;i++)
{
for(j=0;j<n;j++)
{
if(visit[i][j]>7)
{
printf("No\n");
break;
}
}
if(j<n)
break;
}
if(i==n)
printf("Yes\n");
}
return 0;
}
HDU-1869-六度分离