首页 > 代码库 > hdu1869六度分离,spfa实现求最短路
hdu1869六度分离,spfa实现求最短路
就是给一个图,如果任意两点之间的距离都不超过7则输出Yes,否则
输出No。
由于之前没写过spfa,无聊的试了一下。
大概说下我对spfa实现的理解。
由于它是bellmanford的优化,
所以之前会bf的理解起来,可能会比较容易。
它是这样子的,你弄一个队列,
先打一个起点进去,之后求出的到各点的最短路,
都是由这个点出发的。
然后开始迭代,直至队列为空,
在迭代的过程中,
首先从队列里面拿一个点出来,
然后标记一下,说明这个点不在队列里面,
然后开始枚举所有点,进行松弛化,
松弛化的过程就是看以这个拿出来的点为转折点,
枚举的其它点为终点,看有没有更好的方法
让路径变短。
如果有的话,判断那个点在不在队列中,
如果不在,
就把枚举出的那个点,拿到
队列中去,记得标记一下说明这个点已经在队列中了。
就是这样了。
代码如下:
输出No。
由于之前没写过spfa,无聊的试了一下。
大概说下我对spfa实现的理解。
由于它是bellmanford的优化,
所以之前会bf的理解起来,可能会比较容易。
它是这样子的,你弄一个队列,
先打一个起点进去,之后求出的到各点的最短路,
都是由这个点出发的。
然后开始迭代,直至队列为空,
在迭代的过程中,
首先从队列里面拿一个点出来,
然后标记一下,说明这个点不在队列里面,
然后开始枚举所有点,进行松弛化,
松弛化的过程就是看以这个拿出来的点为转折点,
枚举的其它点为终点,看有没有更好的方法
让路径变短。
如果有的话,判断那个点在不在队列中,
如果不在,
就把枚举出的那个点,拿到
队列中去,记得标记一下说明这个点已经在队列中了。
就是这样了。
代码如下:
#include<iostream> #include<cstring> #include<queue> using namespace std; int num_dot,num_side,iq[110],weight[110],dis[110][110]; void init() { int i,t1,t2; memset(dis,127,sizeof(dis)); for(i=0;i<num_side;i++) { scanf("%d%d",&t1,&t2); dis[t1][t2]=1; dis[t2][t1]=1; } } void spfa(int st) { int x,i; queue<int>qq; memset(iq,0,sizeof(iq)); memset(weight,127,sizeof(weight)); iq[st]=1; qq.push(st); weight[st]=0; while(qq.size()) { x=qq.front(); qq.pop(); iq[x]=0; for(i=0;i<num_dot;i++) if(weight[i]>weight[x]+dis[x][i]) { weight[i]=weight[x]+dis[x][i]; if(!iq[i]) { qq.push(i); iq[i]=1; } } } } bool isright() { int i,j; for(i=0;i<num_dot;i++) { spfa(i); for(j=i+1;j<num_dot;j++) if(weight[j]>7) return 0; } return 1; } int main() { while(scanf("%d%d",&num_dot,&num_side)!=EOF) {init(); if(isright()) printf("Yes\n"); else printf("No\n");} }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。