# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
864518 |
2023-10-23T07:02:08 Z |
maks007 |
Toll (BOI17_toll) |
C++14 |
|
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]) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
525 ms |
6480 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
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 |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
0 ms |
596 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Incorrect |
525 ms |
6480 KB |
Output isn't correct |
2 |
Halted |
0 ms |
0 KB |
- |