Submission #971852

#	Time	Username	Problem	Language	Result	Execution time	Memory
971852		THXuan	Airplane (NOI23_airplane)	C++14	100 / 100	289 ms	27252 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <queue>
#include <set>
#include <map>
#define INF 1e18
using namespace std;
typedef long long ll;

vector<int>adj[200005];
ll h[200005], d[200005], dd[200005];
bool visited[200005];

void solve()
{
	int n, m; cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> h[i];
	for (int i = 1; i <= m; i++) {
		int u, v; cin >> u >> v;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	for (int i = 1; i <= n; i++) { d[i] = INF; dd[i] = INF; }
	using T = pair<ll, int>;
	priority_queue<T, vector<T>, greater<T>>pq;
	d[1] = 0;
	pq.push({ 0, 1 });
	while (pq.size()) {
		int a = pq.top().second; pq.pop();
		if (visited[a]) continue;
		visited[a] = true;
		for (auto u : adj[a]) {
			if (d[u] > max(h[u], d[a] + 1)) {
				d[u] = max(h[u], d[a] + 1);
				pq.push({ d[u], u });
			}
		}
	}
	dd[n] = 0;
	pq.push({ 0, n });
	for (int i = 1; i <= n; i++) visited[i] = false;
	while (pq.size()) {
		int a = pq.top().second; pq.pop();
		if (visited[a]) continue;
		visited[a] = true;
		for (auto u : adj[a]) {
			if (dd[u] > max(h[u], dd[a] + 1)) {
				dd[u] = max(h[u], dd[a] + 1);
				pq.push({ dd[u], u });
			}
		}
	}
	ll ans = INF;
	for (int i = 1; i <= n; i++) {
		if (d[i] == dd[i])ans = min(ans, d[i] + dd[i]);
		for (auto u : adj[i]) {
			if (d[i] == dd[u])ans = min(ans, d[i] + dd[u] + 1);
		}
	}
	cout << ans << "\n";
}

int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	int t = 1;// cin>>t;
	while (t--) solve();
	return 0;
}

• Subtask 1: 22 / 22
• Subtask 2: 10 / 10
• Subtask 3: 31 / 31
• Subtask 4: 37 / 37