单源最短路径SPFA---zoj3146

          针对Bellman-Ford算法效率比较低的问题，SPFA是用一个队列来进行维护。初始时将源加入队列。每次从队列中取出一个元素，并对所有与他相邻的点进行松弛，若某个相邻的点松弛成功，则将其入队。直到队列为空时算法结束。它可以在O(kE)的时间复杂度内求出源点到其他所有点的最短路径，有办法证明对于通常的情况，k在2左右。

         值得注意的一点是，如果某个点进入队列的次数超过V次则图中存在负环（SPFA无法处理带负环的图）。

#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
using namespace std;
class node
{
public:
	int r,c;
	node(){}
	node(int r,int c):r(r),c(c){}
};
class edge
{
public:
	int sr,sc,er,ec;
	int cost;
	edge(){}
	edge(int sr,int sc,int er,int ec,int cost):sr(sr),sc(sc),er(er),ec(ec),cost(cost)
	{
	}
};
int n,m,r,c;
int map[31][31];
int dist[31][31];
int flag[31][31];
const int maximum=1<<30;
vector<edge>a[31][31];

void init()
{
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
	a[i][j].clear();
	for(int i=0;i<n;i++)
	{
		for(int j=0;j<m;j++)
		{
			if(map[i][j]==0)
				continue;
			int d;
			int west=j-map[i][j];
			if(west<0)
			{
				edge e(i,j,i,0,map[i][j]);
				a[i][j].push_back(e);	
			}
			else
			{
				edge e(i,j,i,west,map[i][j]);
				a[i][j].push_back(e);
			}		
			int east=j+map[i][j];
			if(east>=m)
			{
				edge e(i,j,i,m-1,map[i][j]);
				a[i][j].push_back(e);
			}
			else
			{
				edge e(i,j,i,east,map[i][j]);
				a[i][j].push_back(e);
			}
			int north=i-map[i][j];
			if(north<0)
			{
				edge e(i,j,0,j,map[i][j]);
				a[i][j].push_back(e);
			}
			else
			{
				edge e(i,j,north,j,map[i][j]);
				a[i][j].push_back(e);
			}
			int south=i+map[i][j];
			if(south>=n)
			{
				edge e(i,j,n-1,j,map[i][j]);
				a[i][j].push_back(e);
			}
			else
			{
				edge e(i,j,south,j,map[i][j]);
				a[i][j].push_back(e);
			}	
		}
	}		
}
bool SPFA()
{
	for(int i=0;i<n;i++)
	for(int j=0;j<m;j++)
		dist[i][j]=maximum;
	memset(flag,0,sizeof(flag));
	dist[r-1][c-1]=0;
	queue<node>q;
	q.push(node(r-1,c-1));
	flag[r-1][c-1]=1;;
	while(!q.empty())
	{
		node n=q.front();
		q.pop();
		int row=n.r;
		int col=n.c;
		flag[row][col]=0;
		int size=a[row][col].size();
		for(int i=0;i<size;i++)
		{
			int startr=(a[row][col])[i].sr;
			int startc=(a[row][col])[i].sc;
			int endr=(a[row][col])[i].er;
			int endc=(a[row][col])[i].ec;
			int cost=(a[row][col])[i].cost;
			if(dist[startr][startc]!=maximum&&dist[startr][startc]+cost<dist[endr][endc])
			{
				dist[endr][endc]=dist[startr][startc]+cost;
				if(flag[endr][endc]==0)
				{
				
					q.push(node(endr,endc));
					flag[endr][endc]==1;
				}		
			}	
		}	
	}
	return true;
}
int main()
{
	while(cin>>n>>m>>r>>c)
	{
		int fr,fc;
		for(int i=0;i<n;i++)
		for(int j=0;j<m;j++)
		{	
			cin>>map[i][j];
			if(map[i][j]==0)
			{
				fr=i;
				fc=j;	
			}
		}
		init();
		SPFA();
		if(dist[fr][fc]!=maximum)
		cout<<dist[fr][fc]<<endl;
		else
		cout<<"No solution"<<endl;
	}	
}