单源最短路径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;elsecout<<"No solution"<<endl;}}

???

???????

?????