首页 > 代码库 > HDU1869 六度分离

HDU1869 六度分离

2024-07-18 22:24:43   211人阅读

 

题目链接:http://acm.hdu.edu.cn/showproblem.php?pid=1869

解题思路：Floyd算法

Floyd算法：找到A->B的最短路径。从A->B的路径不在乎两种情况，1）直接从A->B；2）从A经过X个点后到达B,即A->X->B.这时只要选择这两种情况的最小值，就是A->B的最短路径。即d(AB)=min(d(AB),d(AX)+d(XB))。核心代码如下：

for(int k=0;k<n;k++)
     for(int i=0;i<n;i++)
          for(int j=0;j<n;j++)
              d[i][j]=d(map[i][k]+d[k][j],d[i][j]);

 下面贴上我的代码：

#include <iostream>#include <algorithm>#include <cstdio>using namespace std;const int INF=0x3f3f3f;int map[205][205];int main(){    int n,m,a,b,flag;    while(scanf("%d%d",&n,&m)!=EOF)    {        for(int i=0;i<n;i++)        {            for(int j=0;j<n;j++)                map[i][j]=INF;            map[i][i]=0;        }        for(int i=0;i<m;i++)        {            scanf("%d%d",&a,&b);            map[a][b]=map[b][a]=1;        }        for(int k=0;k<n;k++)            for(int i=0;i<n;i++)                for(int j=0;j<n;j++)                  map[i][j]=min(map[i][k]+map[k][j],map[i][j]);        flag=0;        for(int i=0;i<n;i++)        {            for(int j=0;j<n;j++)               if(map[i][j]>7)                  flag=1;            if(flag)                break;        }        if(flag)            cout<<"No"<<endl;        else cout<<"Yes"<<endl;    }    return 0;}

 


联系
我们