oj.uz

Submission #1059068

# Submission time Handle Problem Language Result Execution time Memory
1059068 2024-08-14T16:44:16 Z vjudge1 Cyberland (APIO23_cyberland) C++17
0 / 100
 15 ms 6748 KB 
#include "cyberland.h"
#include <queue>
// #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);
		}
	}
	int path[N];
	for (int i = 0; i < N; i++) {
		if (!vis[i]) arr[i] = 1;
		vis[i] = false;
		path[i] = 1e9;
	}
	/* for (int i = 0; i < N; i++) cerr << arr[i] << ' ';
	cerr << endl; */
	priority_queue <pair <int, 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.0 / 5.0

# Verdict Execution time Memory Grader output
1 Incorrect 10 ms 856 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #2
0.0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 11 ms 1116 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #3
0.0 / 13.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1116 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #4
0.0 / 19.0

# Verdict Execution time Memory Grader output
1 Incorrect 15 ms 6748 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 12 ms 1372 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #6
0.0 / 16.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1224 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #7
0.0 / 29.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1116 KB Wrong Answer.
2 Halted 0 ms 0 KB -

Subtask #8
0.0 / 3.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 1116 KB Wrong Answer.
2 Halted 0 ms 0 KB -