hdu1869六度分开，spfa实现求最短路

hdu1869六度分离，spfa实现求最短路
就是给一个图，如果任意两点之间的距离都不超过7则输出Yes，否则

输出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");}
}

hdu1869六度分开，spfa实现求最短路

相关推荐