# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
385035 |
2021-04-03T03:12:17 Z |
timmyfeng |
Robot (JOI21_ho_t4) |
C++17 |
|
1058 ms |
70576 KB |
#include <bits/stdc++.h>
using namespace std;
const int N = 100001;
map<int, vector<array<long long, 2>>> adj[N];
priority_queue<array<long long, 3>> que;
map<int, long long> dist[N];
void update(int c, int x, long long d) {
if (dist[c].count(x) == 0 || d < dist[c][x]) {
que.push({-d, c, x});
dist[c][x] = d;
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int n, m;
cin >> n >> m;
while (m--) {
int u, v, c, p;
cin >> u >> v >> c >> p;
adj[u][c].push_back({v, p});
adj[v][c].push_back({u, p});
}
que.push({0, 1, 0});
dist[1][0] = 0;
while (!que.empty()) {
auto [d, u, x] = que.top();
que.pop();
d = -d;
if (d > dist[u][x]) {
continue;
}
if (x == 0) {
for (auto &[y, v] : adj[u]) {
long long sum = 0;
for (auto [c, w] : v) {
sum += w;
}
for (auto [c, w] : v) {
update(c, 0, d + min(w, sum - w));
update(c, y, d);
}
}
} else {
long long sum = 0;
for (auto [c, w] : adj[u][x]) {
sum += w;
}
for (auto [c, w] : adj[u][x]) {
update(c, 0, d + sum - w);
}
}
}
cout << (dist[n].count(0) == 0 ? -1 : dist[n][0]) << "\n";
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
7 ms |
9708 KB |
Output is correct |
4 |
Correct |
7 ms |
9708 KB |
Output is correct |
5 |
Correct |
7 ms |
9708 KB |
Output is correct |
6 |
Correct |
8 ms |
9708 KB |
Output is correct |
7 |
Correct |
8 ms |
9836 KB |
Output is correct |
8 |
Correct |
8 ms |
9836 KB |
Output is correct |
9 |
Correct |
11 ms |
10348 KB |
Output is correct |
10 |
Correct |
10 ms |
10220 KB |
Output is correct |
11 |
Correct |
9 ms |
10092 KB |
Output is correct |
12 |
Correct |
9 ms |
10092 KB |
Output is correct |
13 |
Correct |
10 ms |
10092 KB |
Output is correct |
14 |
Correct |
10 ms |
10092 KB |
Output is correct |
15 |
Correct |
10 ms |
9964 KB |
Output is correct |
16 |
Correct |
12 ms |
10092 KB |
Output is correct |
17 |
Correct |
9 ms |
10092 KB |
Output is correct |
18 |
Correct |
9 ms |
9836 KB |
Output is correct |
19 |
Correct |
10 ms |
9964 KB |
Output is correct |
20 |
Correct |
9 ms |
10092 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
285 ms |
25760 KB |
Output is correct |
2 |
Correct |
90 ms |
18072 KB |
Output is correct |
3 |
Correct |
271 ms |
23564 KB |
Output is correct |
4 |
Correct |
142 ms |
20920 KB |
Output is correct |
5 |
Correct |
986 ms |
64924 KB |
Output is correct |
6 |
Correct |
727 ms |
56556 KB |
Output is correct |
7 |
Correct |
446 ms |
44228 KB |
Output is correct |
8 |
Correct |
417 ms |
41324 KB |
Output is correct |
9 |
Correct |
446 ms |
41196 KB |
Output is correct |
10 |
Correct |
347 ms |
35360 KB |
Output is correct |
11 |
Correct |
113 ms |
20844 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
7 ms |
9708 KB |
Output is correct |
2 |
Correct |
7 ms |
9708 KB |
Output is correct |
3 |
Correct |
7 ms |
9708 KB |
Output is correct |
4 |
Correct |
7 ms |
9708 KB |
Output is correct |
5 |
Correct |
7 ms |
9708 KB |
Output is correct |
6 |
Correct |
8 ms |
9708 KB |
Output is correct |
7 |
Correct |
8 ms |
9836 KB |
Output is correct |
8 |
Correct |
8 ms |
9836 KB |
Output is correct |
9 |
Correct |
11 ms |
10348 KB |
Output is correct |
10 |
Correct |
10 ms |
10220 KB |
Output is correct |
11 |
Correct |
9 ms |
10092 KB |
Output is correct |
12 |
Correct |
9 ms |
10092 KB |
Output is correct |
13 |
Correct |
10 ms |
10092 KB |
Output is correct |
14 |
Correct |
10 ms |
10092 KB |
Output is correct |
15 |
Correct |
10 ms |
9964 KB |
Output is correct |
16 |
Correct |
12 ms |
10092 KB |
Output is correct |
17 |
Correct |
9 ms |
10092 KB |
Output is correct |
18 |
Correct |
9 ms |
9836 KB |
Output is correct |
19 |
Correct |
10 ms |
9964 KB |
Output is correct |
20 |
Correct |
9 ms |
10092 KB |
Output is correct |
21 |
Correct |
285 ms |
25760 KB |
Output is correct |
22 |
Correct |
90 ms |
18072 KB |
Output is correct |
23 |
Correct |
271 ms |
23564 KB |
Output is correct |
24 |
Correct |
142 ms |
20920 KB |
Output is correct |
25 |
Correct |
986 ms |
64924 KB |
Output is correct |
26 |
Correct |
727 ms |
56556 KB |
Output is correct |
27 |
Correct |
446 ms |
44228 KB |
Output is correct |
28 |
Correct |
417 ms |
41324 KB |
Output is correct |
29 |
Correct |
446 ms |
41196 KB |
Output is correct |
30 |
Correct |
347 ms |
35360 KB |
Output is correct |
31 |
Correct |
113 ms |
20844 KB |
Output is correct |
32 |
Correct |
157 ms |
23272 KB |
Output is correct |
33 |
Correct |
227 ms |
25440 KB |
Output is correct |
34 |
Correct |
480 ms |
41372 KB |
Output is correct |
35 |
Correct |
413 ms |
34772 KB |
Output is correct |
36 |
Correct |
354 ms |
41408 KB |
Output is correct |
37 |
Correct |
422 ms |
43988 KB |
Output is correct |
38 |
Correct |
435 ms |
54336 KB |
Output is correct |
39 |
Correct |
172 ms |
26980 KB |
Output is correct |
40 |
Correct |
431 ms |
46572 KB |
Output is correct |
41 |
Correct |
498 ms |
46828 KB |
Output is correct |
42 |
Correct |
554 ms |
50460 KB |
Output is correct |
43 |
Correct |
225 ms |
28136 KB |
Output is correct |
44 |
Correct |
513 ms |
34916 KB |
Output is correct |
45 |
Correct |
337 ms |
42092 KB |
Output is correct |
46 |
Correct |
275 ms |
42348 KB |
Output is correct |
47 |
Correct |
357 ms |
43724 KB |
Output is correct |
48 |
Correct |
1058 ms |
70576 KB |
Output is correct |