Submission #1156613

#	Time	Username	Problem	Language	Result	Execution time	Memory
1156613		pinbu	Airplane (NOI23_airplane)	C++20	100 / 100	178 ms	20660 KiB

Main

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

const int N = 200005, oo = 1e9 + 7;

int n, m, a[N];
array<int, 2> e[2 * N];
vector<int> adj[N];
int d1[N], dn[N];
void Dijkstra(int s, int *d) {
	fill(d + 1, d + 1 + n, oo);
	d[s] = 0;
	priority_queue<pair<int, int>> pq;
	pq.emplace(0, s);
	while (pq.size()) {
		int u = pq.top().second, di = -pq.top().first;
		pq.pop();
		if (d[u] != di) continue;
		for (int v: adj[u]) {
			if (d[v] > max(d[u] + 1, a[v])) {
				pq.emplace(-(d[v] = max(d[u] + 1, a[v])), v);
			}
		}
	}
}
void solve(void) {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) cin >> a[i];
	for (int i = 1, u, v; i <= m; i++) {
		cin >> u >> v;
		e[i] = {u, v};
		adj[u].emplace_back(v);
		adj[v].emplace_back(u);
	}
	Dijkstra(1, d1); Dijkstra(n, dn);
	int ans = oo;
	for (int i = 1; i <= n; i++) {
		ans = min(ans, 2 * max(d1[i], dn[i]));
	}
	for (int i = 1; i <= m; i++) {
		int u = e[i][0], v = e[i][1];
		ans = min(ans, 2 * min(max(d1[u], dn[v]), max(d1[v], dn[u])) + 1);
	}
	cout << ans;
}

signed main(void) {
    ios::sync_with_stdio(false); cin.tie(nullptr);
    
    int TEST = 1;
    while (TEST--) solve();
    
    return 0;
}

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