正经题解｜Kingdom Game II

题意解析

在一个地图当中，给出$k$个起点，$m$个终点，和每个起点出发的时间，求出到达所有终点所需要的最短时间。

其中只要任意一个起点到达终点即可算到达。

思路解析

在这道题目当中，我们需要考虑到每个起点的出发时间，以及在运算过程当中，优先计算时间较短的状态，这样子才可以让最终到达目标的状态一定是所有时间当中最短的。

跟常规的BFS相比，多了一件需要判断最小值优先搜索的情况，那么使用priority_queue来进行维护，优先让时间较小的状态出队即可

时间复杂度分析

$O(n^2*log(n))$

STD标程

#include<bits/stdc++.h>
using namespace std;

struct Node{
	int x,y,step;
	friend bool operator < (Node a,Node b){
		return a.step > b.step;
	}
};
int mp[5005][5005];
bool vis[5005][5005];
priority_queue<Node> q;
int dir[4][2] = {1,0,-1,0,0,1,0,-1};
int n,m,k,a,b,s;

bool check(int x,int y ){
	return x >= 1 && x <= n && y >= 1 && y <= n && !vis[x][y];
}

int bfs(){
	int cnt = 0 ;
	while(!q.empty()){
		Node fr = q.top();
		q.pop();
		vis[fr.x][fr.y] = true;
		// cout << fr.x << " " << fr.y << endl;
		if(mp[fr.x][fr.y]){
			cnt ++ ;
		}
		if(cnt >= m){
			return fr.step;
		}
		for(int i = 0 ; i < 4 ; i ++ ){
			int tx = dir[i][0] + fr.x ;
			int ty = dir[i][1] + fr.y;
			if(check(tx,ty)){
				vis[tx][ty] = true;
				q.push({tx,ty,fr.step+1});
			}
		}
	}
}

int main()
{

	cin >> n >> m >> k;
	for(int i = 0 ; i < m ; i ++){
		cin >> a >> b;
		mp[a][b] = 1;
	}
	int cnt = 0 ;
	for(int i = 0 ; i < k ; i ++ ){
		cin >> a >> b >> s;
		q.push({a,b,s});	
	}

	cout << bfs() << endl;
	
	
	
	return 0;
}