Submission #1059088

#	Time	Username	Problem	Language	Result	Execution time	Memory
1059088		vjudge1	Cyberland (APIO23_cyberland)	C++17	44 / 100	25 ms	8028 KiB

cyberland

#include "cyberland.h"
#include <queue>
#include <cstdint>
// #include <iostream>
using namespace std;

double solve(int N, int M, int K, int H, vector <int> x, vector <int> y, vector <int> c, vector <int> arr) {
	vector <pair <int, int>> graph[N];
	for (int i = 0; i < M; i++) {
		graph[x[i]].emplace_back(y[i], c[i]);
		graph[y[i]].emplace_back(x[i], c[i]);
	}
	queue <int> bfs;
	bool vis[N] = {};
	bfs.push(0);
	vis[0] = vis[H] = true;
	arr[0] = 0;
	while (!bfs.empty()) {
		int u = bfs.front();
		bfs.pop();
		for (auto &[v, w] : graph[u]) {
			if (vis[v]) continue;
			vis[v] = true;
			bfs.push(v);
		}
	}
	int64_t path[N];
	for (int i = 0; i < N; i++) {
		if (!vis[i]) arr[i] = 1;
		vis[i] = false;
		path[i] = 1e17;
	}
	/* for (int i = 0; i < N; i++) cerr << arr[i] << ' ';
	cerr << endl; */
	priority_queue <pair <int64_t, int>> q;
	q.emplace(0, H);
	path[H] = 0;
	while (!q.empty()) {
		int u = q.top().second;
		q.pop();
		if (vis[u]) continue;
		vis[u] = true;
		if (!arr[u]) return path[u];
		for (auto &[v, w] : graph[u]) {
			if (!vis[v] && path[v] > path[u] + w) {
				path[v] = path[u] + w;
				q.emplace(-path[v], v);
			}
		}
	}
	return -1;
}

• Subtask 1: 0 / 5
• Subtask 2: 8 / 8
• Subtask 3: 13 / 13
• Subtask 4: 0 / 19
• Subtask 5: 7 / 7
• Subtask 6: 16 / 16
• Subtask 7: 0 / 29
• Subtask 8: 0 / 3