# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
388882 |
2021-04-13T08:49:47 Z |
Vlatko |
Robot (JOI21_ho_t4) |
C++17 |
|
1087 ms |
84308 KB |
// Note: This solution is from usaco.guide
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
const ll inf = 1e18;
const int N = 100010;
struct Edge {
int to, c;
ll p;
};
int n, m;
map<int, vector<Edge>> graph[N]; // graph[node][edge color]
ll dist[N]; // d[node] = distance, entered through an edge that won't be touched again
map<int, ll> dist2[N]; // d2[node][edge color c] = distance, but entered through c, must exit through c by recoloring all adjacent (including the one we entered through)
map<int, ll> psum[N]; // csum[node][edge color] = sum of weights
int main() {
cin.tie(0)->sync_with_stdio(0);
cin >> n >> m;
for (int i = 0; i < m; ++i) {
int a, b, c, p;
cin >> a >> b >> c >> p;
graph[a][c].push_back({b, c, p});
graph[b][c].push_back({a, c, p});
psum[a][c] += p;
psum[b][c] += p;
}
for (int i = 1; i <= n; ++i) {
dist[i] = inf;
}
dist[1] = 0;
using pqState = tuple<ll, int, int>; // d, u, c (color of back edge)
priority_queue<pqState, vector<pqState>, greater<pqState>> pq;
pq.emplace(0, 1, 0);
while (!pq.empty()) {
ll dist_node;
int node, bkc; // node, back color
tie(dist_node, node, bkc) = pq.top();
pq.pop();
if (bkc > 0) {
// special case: dp2
if (dist_node != dist2[node][bkc]) continue;
for (Edge e : graph[node][bkc]) {
// must exit through same colored edge and flip all others
ll alt = dist_node + psum[node][bkc] - e.p;
if (alt < dist[e.to]) {
dist[e.to] = alt;
pq.emplace(alt, e.to, 0);
}
}
} else {
if (dist_node != dist[node]) continue;
for (auto& kvp : graph[node]) {
for (Edge e : kvp.second) {
ll alt;
// case 1: don't recolor e, recolor all except e
alt = dist_node + psum[node][e.c] - e.p;
if (alt < dist[e.to]) {
dist[e.to] = alt;
pq.emplace(alt, e.to, 0);
}
// case 2: recolor only e and no other
alt = dist_node + e.p;
if (alt < dist[e.to]) {
dist[e.to] = alt;
pq.emplace(alt, e.to, 0);
}
// case 3: don't recolor e NOW, but must recolor all adjacent next node
alt = dist_node;
if (!dist2[e.to].count(e.c) || alt < dist2[e.to][e.c]) {
dist2[e.to][e.c] = alt;
pq.emplace(alt, e.to, e.c);
}
}
}
}
}
cout << (dist[n] == inf ? -1 : dist[n]) << '\n';
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
14412 KB |
Output is correct |
2 |
Correct |
10 ms |
14412 KB |
Output is correct |
3 |
Correct |
9 ms |
14412 KB |
Output is correct |
4 |
Correct |
9 ms |
14320 KB |
Output is correct |
5 |
Correct |
9 ms |
14412 KB |
Output is correct |
6 |
Correct |
9 ms |
14420 KB |
Output is correct |
7 |
Correct |
10 ms |
14560 KB |
Output is correct |
8 |
Correct |
10 ms |
14412 KB |
Output is correct |
9 |
Correct |
13 ms |
15052 KB |
Output is correct |
10 |
Correct |
12 ms |
14960 KB |
Output is correct |
11 |
Correct |
11 ms |
14824 KB |
Output is correct |
12 |
Correct |
11 ms |
14664 KB |
Output is correct |
13 |
Correct |
11 ms |
14684 KB |
Output is correct |
14 |
Correct |
11 ms |
14780 KB |
Output is correct |
15 |
Correct |
10 ms |
14688 KB |
Output is correct |
16 |
Correct |
11 ms |
14688 KB |
Output is correct |
17 |
Correct |
11 ms |
14812 KB |
Output is correct |
18 |
Correct |
12 ms |
14540 KB |
Output is correct |
19 |
Correct |
11 ms |
14668 KB |
Output is correct |
20 |
Correct |
11 ms |
14684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
235 ms |
34436 KB |
Output is correct |
2 |
Correct |
97 ms |
24632 KB |
Output is correct |
3 |
Correct |
252 ms |
31572 KB |
Output is correct |
4 |
Correct |
154 ms |
27708 KB |
Output is correct |
5 |
Correct |
1076 ms |
82264 KB |
Output is correct |
6 |
Correct |
932 ms |
71888 KB |
Output is correct |
7 |
Correct |
404 ms |
56340 KB |
Output is correct |
8 |
Correct |
473 ms |
50828 KB |
Output is correct |
9 |
Correct |
525 ms |
50908 KB |
Output is correct |
10 |
Correct |
375 ms |
47860 KB |
Output is correct |
11 |
Correct |
164 ms |
32672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
14412 KB |
Output is correct |
2 |
Correct |
10 ms |
14412 KB |
Output is correct |
3 |
Correct |
9 ms |
14412 KB |
Output is correct |
4 |
Correct |
9 ms |
14320 KB |
Output is correct |
5 |
Correct |
9 ms |
14412 KB |
Output is correct |
6 |
Correct |
9 ms |
14420 KB |
Output is correct |
7 |
Correct |
10 ms |
14560 KB |
Output is correct |
8 |
Correct |
10 ms |
14412 KB |
Output is correct |
9 |
Correct |
13 ms |
15052 KB |
Output is correct |
10 |
Correct |
12 ms |
14960 KB |
Output is correct |
11 |
Correct |
11 ms |
14824 KB |
Output is correct |
12 |
Correct |
11 ms |
14664 KB |
Output is correct |
13 |
Correct |
11 ms |
14684 KB |
Output is correct |
14 |
Correct |
11 ms |
14780 KB |
Output is correct |
15 |
Correct |
10 ms |
14688 KB |
Output is correct |
16 |
Correct |
11 ms |
14688 KB |
Output is correct |
17 |
Correct |
11 ms |
14812 KB |
Output is correct |
18 |
Correct |
12 ms |
14540 KB |
Output is correct |
19 |
Correct |
11 ms |
14668 KB |
Output is correct |
20 |
Correct |
11 ms |
14684 KB |
Output is correct |
21 |
Correct |
235 ms |
34436 KB |
Output is correct |
22 |
Correct |
97 ms |
24632 KB |
Output is correct |
23 |
Correct |
252 ms |
31572 KB |
Output is correct |
24 |
Correct |
154 ms |
27708 KB |
Output is correct |
25 |
Correct |
1076 ms |
82264 KB |
Output is correct |
26 |
Correct |
932 ms |
71888 KB |
Output is correct |
27 |
Correct |
404 ms |
56340 KB |
Output is correct |
28 |
Correct |
473 ms |
50828 KB |
Output is correct |
29 |
Correct |
525 ms |
50908 KB |
Output is correct |
30 |
Correct |
375 ms |
47860 KB |
Output is correct |
31 |
Correct |
164 ms |
32672 KB |
Output is correct |
32 |
Correct |
162 ms |
28380 KB |
Output is correct |
33 |
Correct |
197 ms |
29216 KB |
Output is correct |
34 |
Correct |
458 ms |
50096 KB |
Output is correct |
35 |
Correct |
351 ms |
41508 KB |
Output is correct |
36 |
Correct |
388 ms |
46892 KB |
Output is correct |
37 |
Correct |
419 ms |
49252 KB |
Output is correct |
38 |
Correct |
397 ms |
55668 KB |
Output is correct |
39 |
Correct |
190 ms |
31840 KB |
Output is correct |
40 |
Correct |
490 ms |
52192 KB |
Output is correct |
41 |
Correct |
530 ms |
52236 KB |
Output is correct |
42 |
Correct |
571 ms |
60988 KB |
Output is correct |
43 |
Correct |
250 ms |
36916 KB |
Output is correct |
44 |
Correct |
513 ms |
42740 KB |
Output is correct |
45 |
Correct |
367 ms |
47556 KB |
Output is correct |
46 |
Correct |
323 ms |
47944 KB |
Output is correct |
47 |
Correct |
365 ms |
49180 KB |
Output is correct |
48 |
Correct |
1087 ms |
84308 KB |
Output is correct |