Submission #1149897

#	Time	Username	Problem	Language	Result	Execution time	Memory
1149897		xnqs	Airplane (NOI23_airplane)	C++20	0 / 100	1088 ms	328596 KiB

Main

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <unordered_map>
#include <tuple>

int gs, edg;
std::vector<int> node_altitude;
std::vector<std::vector<int>> adj_list;

void build_graph() {
	std::cin >> gs >> edg;
	node_altitude.resize(gs+1);
	adj_list.resize(gs+1);

	for (int i = 1; i <= gs; i++) {
		std::cin >> node_altitude[i];
	}

	for (int i = 0, a, b; i < edg; i++) {
		std::cin >> a >> b;
		adj_list[a].emplace_back(b);
		adj_list[b].emplace_back(a);
	}
}

bool can_improve(std::unordered_map<int,int>& map, int pos, int val) {
	if (!map.count(pos)) {
		return 1;
	}
	return map[pos] > val;
}

void shortest_path() {
	std::vector<std::unordered_map<int,int>> dist(gs+1);
	std::priority_queue<std::tuple<int,int,int>, std::vector<std::tuple<int,int,int>>, std::greater<std::tuple<int,int,int>>> pq;

	pq.emplace(0,1,0);
	dist[1][0] = 0;

	while (!pq.empty()) {
		auto [c, k, h] = pq.top();
		pq.pop();

		for (const auto& i : adj_list[k]) {
			if (node_altitude[i] <= h) {
				if (can_improve(dist[i],h,dist[k][h]+1)) {
					dist[i][h] = dist[k][h]+1;
					pq.emplace(dist[i][h],i,h);
				}
			}
			if (node_altitude[i] >= h) {
				if (can_improve(dist[i],node_altitude[i],dist[k][h]+std::max(0,node_altitude[i]-h-1)+1)) {
					dist[i][node_altitude[i]] = dist[k][h] + std::max(0, node_altitude[i]-h-1) + 1;
					pq.emplace(dist[i][node_altitude[i]], i, node_altitude[i]);
				}
			}
			if (node_altitude[i] < h) {
				if (h-1 >= 0 && can_improve(dist[i],h-1,dist[k][h]+1)) {
					dist[i][h-1] = dist[k][h]+1;
					pq.emplace(dist[i][h-1],i,h-1);
				}
			}
		}
	}

	int ret = 0x7f7f7f7f;
	for (const auto& i : dist[gs]) {
		ret = std::min(ret, i.second + i.first);
	}

	std::cout << ret << "\n";
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	build_graph();
	shortest_path();
}

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