# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
375759 |
2021-03-10T00:37:23 Z |
rama_pang |
Robot (JOI21_ho_t4) |
C++14 |
|
1274 ms |
88848 KB |
#include <bits/stdc++.h>
using namespace std;
using lint = long long;
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int N, M;
cin >> N >> M;
vector<map<int, lint>> S(N);
vector<map<int, vector<pair<int, int>>>> adj(N);
for (int i = 0; i < M; i++) {
int u, v, c, w;
cin >> u >> v >> c >> w;
u--, v--;
S[u][c] += w;
S[v][c] += w;
adj[u][c].push_back({v, w});
adj[v][c].push_back({u, w});
}
// Options when traversing an edge:
// - Change the next road
// - Costs P[e]
// - Change other adjacent road, last road unchanged or has different color
// - Costs S[u][C[e]] - P[e]
// - Change other adjacent road, last road changed and has same color
// - Costs S[u][C[e]] - P[e] - P[last]
//
// dist[u][0] = minimum cost to vertex u, no restrictions
// dist[u][c] = minimum cost to vertex u, where the next road must be of color c (use option 3 next)
vector<map<int, lint>> dist(N);
priority_queue<array<lint, 3>, vector<array<lint, 3>>, greater<array<lint, 3>>> pq;
const auto Relax = [&](int u, int c, lint d) {
if (dist[u].count(c) == 0 || dist[u][c] > d) {
dist[u][c] = d;
pq.push({d, u, c});
}
};
Relax(0, 0, 0);
while (!pq.empty()) {
lint d = pq.top()[0];
int u = (int) pq.top()[1];
int c = (int) pq.top()[2];
pq.pop();
if (dist[u][c] != d) {
continue;
}
if (c == 0) {
for (const auto &adjc : adj[u]) {
for (const auto &[v, w] : adjc.second) {
Relax(v, 0, d + w); // Option 1
Relax(v, 0, d + S[u][adjc.first] - w); // Option 2
Relax(v, adjc.first, d); // Option 3, Part 1
}
}
} else {
for (const auto &[v, w] : adj[u][c]) {
Relax(v, 0, d + S[u][c] - w); // Option 3, Part 2
}
}
}
cout << (dist[N - 1].count(0) ? dist[N - 1][0] : -1) << '\n';
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:57:26: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
57 | for (const auto &[v, w] : adjc.second) {
| ^
Main.cpp:64:24: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
64 | for (const auto &[v, w] : adj[u][c]) {
| ^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
504 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
5 ms |
1132 KB |
Output is correct |
10 |
Correct |
4 ms |
1260 KB |
Output is correct |
11 |
Correct |
3 ms |
876 KB |
Output is correct |
12 |
Correct |
3 ms |
876 KB |
Output is correct |
13 |
Correct |
3 ms |
876 KB |
Output is correct |
14 |
Correct |
3 ms |
876 KB |
Output is correct |
15 |
Correct |
2 ms |
748 KB |
Output is correct |
16 |
Correct |
3 ms |
876 KB |
Output is correct |
17 |
Correct |
3 ms |
896 KB |
Output is correct |
18 |
Correct |
2 ms |
748 KB |
Output is correct |
19 |
Correct |
3 ms |
620 KB |
Output is correct |
20 |
Correct |
2 ms |
876 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
248 ms |
24224 KB |
Output is correct |
2 |
Correct |
104 ms |
13220 KB |
Output is correct |
3 |
Correct |
256 ms |
18248 KB |
Output is correct |
4 |
Correct |
151 ms |
17700 KB |
Output is correct |
5 |
Correct |
1225 ms |
86600 KB |
Output is correct |
6 |
Correct |
956 ms |
74480 KB |
Output is correct |
7 |
Correct |
420 ms |
54472 KB |
Output is correct |
8 |
Correct |
416 ms |
52204 KB |
Output is correct |
9 |
Correct |
430 ms |
52204 KB |
Output is correct |
10 |
Correct |
401 ms |
42024 KB |
Output is correct |
11 |
Correct |
136 ms |
28140 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
384 KB |
Output is correct |
2 |
Correct |
1 ms |
364 KB |
Output is correct |
3 |
Correct |
1 ms |
512 KB |
Output is correct |
4 |
Correct |
1 ms |
384 KB |
Output is correct |
5 |
Correct |
1 ms |
504 KB |
Output is correct |
6 |
Correct |
1 ms |
364 KB |
Output is correct |
7 |
Correct |
2 ms |
512 KB |
Output is correct |
8 |
Correct |
1 ms |
364 KB |
Output is correct |
9 |
Correct |
5 ms |
1132 KB |
Output is correct |
10 |
Correct |
4 ms |
1260 KB |
Output is correct |
11 |
Correct |
3 ms |
876 KB |
Output is correct |
12 |
Correct |
3 ms |
876 KB |
Output is correct |
13 |
Correct |
3 ms |
876 KB |
Output is correct |
14 |
Correct |
3 ms |
876 KB |
Output is correct |
15 |
Correct |
2 ms |
748 KB |
Output is correct |
16 |
Correct |
3 ms |
876 KB |
Output is correct |
17 |
Correct |
3 ms |
896 KB |
Output is correct |
18 |
Correct |
2 ms |
748 KB |
Output is correct |
19 |
Correct |
3 ms |
620 KB |
Output is correct |
20 |
Correct |
2 ms |
876 KB |
Output is correct |
21 |
Correct |
248 ms |
24224 KB |
Output is correct |
22 |
Correct |
104 ms |
13220 KB |
Output is correct |
23 |
Correct |
256 ms |
18248 KB |
Output is correct |
24 |
Correct |
151 ms |
17700 KB |
Output is correct |
25 |
Correct |
1225 ms |
86600 KB |
Output is correct |
26 |
Correct |
956 ms |
74480 KB |
Output is correct |
27 |
Correct |
420 ms |
54472 KB |
Output is correct |
28 |
Correct |
416 ms |
52204 KB |
Output is correct |
29 |
Correct |
430 ms |
52204 KB |
Output is correct |
30 |
Correct |
401 ms |
42024 KB |
Output is correct |
31 |
Correct |
136 ms |
28140 KB |
Output is correct |
32 |
Correct |
156 ms |
11116 KB |
Output is correct |
33 |
Correct |
206 ms |
18020 KB |
Output is correct |
34 |
Correct |
520 ms |
42524 KB |
Output is correct |
35 |
Correct |
395 ms |
34076 KB |
Output is correct |
36 |
Correct |
371 ms |
48792 KB |
Output is correct |
37 |
Correct |
412 ms |
51028 KB |
Output is correct |
38 |
Correct |
478 ms |
60632 KB |
Output is correct |
39 |
Correct |
170 ms |
15204 KB |
Output is correct |
40 |
Correct |
426 ms |
53484 KB |
Output is correct |
41 |
Correct |
477 ms |
53612 KB |
Output is correct |
42 |
Correct |
616 ms |
61208 KB |
Output is correct |
43 |
Correct |
277 ms |
25380 KB |
Output is correct |
44 |
Correct |
526 ms |
26784 KB |
Output is correct |
45 |
Correct |
375 ms |
50284 KB |
Output is correct |
46 |
Correct |
302 ms |
50156 KB |
Output is correct |
47 |
Correct |
420 ms |
50896 KB |
Output is correct |
48 |
Correct |
1274 ms |
88848 KB |
Output is correct |