现在的位置: 首页 > 综合 > 正文

sicily 1321. Robot

2019年11月11日 ⁄ 综合 ⁄ 共 879字 ⁄ 字号 评论关闭

最短路径问题,参考下网上代码

#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;
}

抱歉!评论已关闭.