华为笔试823

第三题：消息传输

在给定的 mxn 网格地图grid中，分布看一些信号塔，用来各区域间通信，每个单元格可以有以下三个状态:

值0代表空地，无法传递信号;

值1代表信号塔A，在收到消息后，信号塔A在1ms后可以将信号发送给上下左右四个方向的信号塔;

值2代表信号塔B，在收到消息后，信号塔B在2ms后可以将信号发送给上下左右四个方向的信号塔，

先给定一个坐标(j,k)输入保证坐标 (j,k)位置一定有信号塔，在坐标(j,k)位置的信号塔触发一个信号

返回 网格地图中所有信号塔收到信号的最小时间，单位为ms。如果不可能，返回-1。

输入

网格的列数n
网格的行数m
触发信号的信号塔坐标(j,k)
第0行网格n个位置的信号塔安装信息(通过空格间隔每个状态值)
第m-1行网格n个位置的信号塔安装信息

输出返回 网格地图中所有信号塔收到信号的最小时间，单位为ms。如果不可能，返回-1。

输入

3
3
1 0
0 1 2
1 2 1
0 1 2

输出

4

思路：dijkstra

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

int main() {
	int n, m;
	cin >> n >> m;
	int x, y;
	cin >> x >> y;
	vector<int> nums(n*m);
	for (int i = 0; i < n*m; i++) {
		cin >> nums[i];
	}
	vector<int> dirt = { -n,n,-1,1 }; //上下左右

	vector<int> dist(n*m, INT_MAX);
	priority_queue < pair<int, int>, vector<pair<int, int>>, greater<>> que;
	//pair<节点最小时间，节点id值>
	dist[x * n + y] = 0;
	que.push({ 0,x * n + y });
	while (!que.empty()) {
		auto a = que.top();
		que.pop();
		int time = a.first;
		int id = a.second;
		if (time > dist[id]) {
			continue;
		}
		for (int dir : dirt) {
			if (id % n == 0 && dir == -1) continue;//左边不能左移
			if ((id+1) % n == 0 && dir == 1) continue;//右边不能右移
			int cur_id = dir + id;
			int cur_time = time + nums[id];
			if (cur_id >= 0 && cur_id < n * m && nums[id] != 0 && cur_time < dist[cur_id]) {
				dist[cur_id] = cur_time;
				que.push({ cur_time ,cur_id });
			}
		}
	}
	auto it = max_element(dist.begin(), dist.end());
	int res = (*it == INT_MAX) ? -1 : *it;
	cout << res << endl;
	return 0;
}