oj.uz

Submission #864518

# Submission time Handle Problem Language Result Execution time Memory
864518 2023-10-23T07:02:08 Z maks007 Toll (BOI17_toll) C++14
10 / 100
 525 ms 7764 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], revG[n];
	for(int i = 0; i < m; i ++) {
		int u, v;
		cin >> u >> v;
		int w;
		cin >> w;
		revG[v].push_back({u, w});
		g[u].push_back({v, w});
	}
	for(auto i : g) {
		sort(i.begin(), i.end(), [](pair <int,int> a, pair <int,int> b) {
			return a.second < b.second;
		});
	}
	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(a == 0) {
			if(dist[b] == 1e9) cout << -1 << "\n";
			else
			cout << dist[b] << "\n"; 
		}else {
			int dp[n];
			for(int i = 0; i < n; i ++) dp[i] = 1e9;
			dp[b] = 0;
			for(int i = 0; i < n; i ++) {
				if(dp[i] != 1e9) {
					for(auto [u, w] : revG[i]) {
						dp[u] = min(dp[u], dp[i] + w);
					}
				}
			}
			if(dp[a] == 1e9) cout << -1 << "\n";
			else cout << dp[a] << "\n";
		}
	}
	return 0;
}

Compilation message

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

Subtask #1
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 525 ms 6480 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 79 ms 6076 KB Output is correct
2 Correct 0 ms 348 KB Output is correct
3 Correct 0 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 0 ms 348 KB Output is correct
6 Correct 0 ms 344 KB Output is correct
7 Correct 15 ms 564 KB Output is correct
8 Correct 18 ms 604 KB Output is correct
9 Correct 49 ms 5980 KB Output is correct
10 Correct 120 ms 7764 KB Output is correct
11 Correct 85 ms 6008 KB Output is correct
12 Correct 65 ms 5712 KB Output is correct
13 Correct 113 ms 7220 KB Output is correct
14 Correct 67 ms 4948 KB Output is correct
15 Correct 57 ms 4436 KB Output is correct
16 Correct 56 ms 4432 KB Output is correct

Subtask #3
0 / 8.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 596 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 596 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 44.0

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