Hud 1869 六度分離[基礎最短路floyd]

題目連接配接：點選打開連結

題目意思很是簡單，每對互相認識權值為1就是了。

WA了很多次，附WA帶代碼。

#include<cstdio>
#include<cstring>
#define INF 0xffffff
#define min(a,b) a>b?b:a

const int N=105;
int dp[N][N];
int n,m;

void Init()
{
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        if(j==i) dp[i][j]=0;
        else dp[i][j]=INF;
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Init();
        int i,j,k;
        for(i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a!=b)
            {
                dp[a][b]=1;
                dp[b][a]=1;
            }
        }
        for(k=0;k<n;k++)
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]);
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            if(dp[i][j]>7) break;
            if(dp[i][j]>7) break;
        }
        if(i==n&&j==n) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}           

很是不了解為什麼會錯，後來，我換了一種判斷成立的方法就AC了，有很是郁悶，判斷的時候為什麼會錯。

後來了就想到了第二個跳出循環的break回出錯，因為每次的j都會為n，而dp[i][n]肯定大于7。我換了一種判斷方法避免了出現這種情況，是以就AC了。

代碼：

#include<cstdio>
#include<cstring>
#define INF 0xffffff
#define min(a,b) a>b?b:a

const int N=105;
int dp[N][N];
int n,m;

void Init()
{
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        if(j==i) dp[i][j]=0;
        else dp[i][j]=INF;
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Init();
        int i,j,k;
        for(i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a!=b)
            {
                dp[a][b]=1;
                dp[b][a]=1;
            }
        }
        for(k=0;k<n;k++)
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]);
        bool flag=false;
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        if(dp[i][j]>7) flag=true;
        if(!flag) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

//AC again
#include<cstdio>
#include<cstring>
#define INF 0xffffff
#define min(a,b) a>b?b:a

const int N=105;
int dp[N][N];
int n,m;

void Init()
{
    for(int i=0;i<n;i++)
    for(int j=0;j<n;j++)
    {
        if(j==i) dp[i][j]=0;
        else dp[i][j]=INF;
    }
}
int main()
{
    while(scanf("%d%d",&n,&m)!=EOF)
    {
        Init();
        int i,j,k;
        for(i=1;i<=m;i++)
        {
            int a,b;
            scanf("%d%d",&a,&b);
            if(a!=b)
            {
                dp[a][b]=1;
                dp[b][a]=1;
            }
        }
        for(k=0;k<n;k++)
        for(i=0;i<n;i++)
        for(j=0;j<n;j++)
        dp[i][j]=min(dp[i][k]+dp[k][j],dp[i][j]);
        for(i=0;i<n;i++)
        {
            for(j=0;j<n;j++)
            if(dp[i][j]>7) break;
            if(dp[i][j]>7&&j!=n) break;
        }
        if(i==n&&j==n) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}
           

最短路，慢慢來。come on！加油！