用广搜实现的spfa

用广搜实现的spfa，如果是用一般的最短路，会发现构图很麻烦，因为它不是路径带权值，而是自身带权值。写起来只要注意，在点出队列的生活将其标记为0，在要压入队列的时候，判断其标记是否为0，为0表示队列中木有这个点，则压入........还有一点，其实这个点即使在队列里面，只要是这个点有比当前的路径短的，就需要更新这个点的最短路，当然，这个点已经在队列里面了，我们就只需要更新它，而不需要把它加入队列......

void dj()

{

	queue<node>q;

	for(ss i=0;i<=n;i++)

	for(ss j=0;j<=n;j++)

	dis[i][j]=maxx;

	dis[n][n]=a[n][n];

	memset(vist,0,sizeof(vist));

	vist[n][n]=1;

	node tmp;

	tmp.x=n;

	tmp.y=n;

	q.push(tmp);

	while(!q.empty())

	{

		node tmp1=q.front();

		q.pop();

		vist[tmp1.x][tmp1.y]=0;

		for(ss i=0;i<4;i++)

		{

			ss xx=tmp1.x+t[i][0];

			ss yy=tmp1.y+t[i][1];

			if(xx>=1&&xx<=n&&yy>=1&&yy<=n&&dis[xx][yy]>dis[tmp1.x][tmp1.y]+a[xx][yy])

			{

				dis[xx][yy]=dis[tmp1.x][tmp1.y]+a[xx][yy];

				if(!vist[xx][yy])

				{

					node tmp2;

					tmp2.x=xx;

					tmp2.y=yy;

					q.push(tmp2);

					vist[xx][yy]=1;

				}

			}

		}

	}

}

巴特西

用广搜实现的spfa

最新文章

热门文章