首页 > 代码库 > HDU1869 六度分离
HDU1869 六度分离
题目链接: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;}
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。