oj.uz

Submission #864505

# Submission time Handle Problem Language Result Execution time Memory
864505 2023-10-23T06:00:27 Z maks007 Toll (BOI17_toll) C++14
10 / 100
 104 ms 6332 KB 
// Bismi ALlah
#include "bits/stdc++.h"

using namespace std;

signed main () {
	int n, m, k, query;
	cin >> k >> n >> m >> query;
	vector<pair <int,int>> g[n];
	for(int i = 0; i < m; i ++) {
		int u, v;
		cin >> u >> v;
		int w;
		cin >> w;
		g[u].push_back({v, w});
	}
	priority_queue <pair <int,int>> q;
	vector <int> dist(n, 1e9);
	dist[0] = 0;
	q.push({0, 0});
	while(!q.empty()) {
		int v = q.top().second, cur_d = q.top().first;
		q.pop();
		if(cur_d > dist[v]) continue;
		for(auto [u, w] : g[v]) {
			if(dist[u] > dist[v] + w) {
				dist[u] = dist[v] + w;
				q.push({-dist[u], u});
			}
		}
	}
	while(query --) {
		int a, b;
		cin >> a >> b;
		if(dist[b] == 1e9) cout << -1 << "\n";
		else
		cout << dist[b] << "\n"; 
	}
	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:25:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   25 |   for(auto [u, w] : g[v]) {
      |            ^

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
10.0 / 10.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 4816 KB Output is correct
2 Correct 0 ms 344 KB Output is correct
3 Correct 0 ms 344 KB Output is correct
4 Correct 0 ms 344 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 0 ms 348 KB Output is correct
7 Correct 15 ms 532 KB Output is correct
8 Correct 16 ms 604 KB Output is correct
9 Correct 45 ms 4088 KB Output is correct
10 Correct 104 ms 6332 KB Output is correct
11 Correct 78 ms 4948 KB Output is correct
12 Correct 61 ms 4432 KB Output is correct
13 Correct 100 ms 6128 KB Output is correct
14 Correct 71 ms 4220 KB Output is correct
15 Correct 52 ms 3644 KB Output is correct
16 Correct 51 ms 3676 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 31.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

# Verdict Execution time Memory Grader output
1 Incorrect 47 ms 4180 KB Output isn't correct
2 Halted 0 ms 0 KB -