最短路径问题,参考下网上代码
#include <iostream> #include <queue> #include <cstring> using namespace std; struct Path { int i, j; int dist; Path(int x, int y, int z){ i = x; j = y; dist = z; } friend bool operator<(const Path &a, const Path b) //优先队列默认从大到小排序,所以这里反过来 {return a.dist > b.dist;} }; int road[101][101]; bool vis[101][101]; int b1,b2,e1,e2,i,j; int dir[4][2] = {-1,0,1,0,0,1,0,-1}; int main(int argc, char const *argv[]) { int t,raws,columns; cin >> t; while(t--) { priority_queue<Path>q; cin >> raws >> columns; for(int k = 1; k <= raws; k++) for(int g = 1; g <= columns; g++) cin >> road[k][g]; memset(vis,false,sizeof(vis)); cin >> b1 >> b2 >> e1 >> e2; vis[b1][b2] = true; Path add = Path(b1,b2,road[b1][b2]); while(!vis[e1][e2]) { for(int k = 0; k < 4; k++) { i = add.i + dir[k][0]; j = add.j + dir[k][1]; if(i <= 0 || i > raws || j <= 0 || j > columns || vis[i][j]) continue; q.push(Path(i,j,add.dist+road[i][j])); } add = q.top(); while(vis[add.i][add.j]){ q.pop(); add = q.top(); } vis[add.i][add.j] = true; } cout << add.dist << endl; } return 0; }