# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
734258 |
2023-05-02T07:42:41 Z |
asdfgrace |
Robot (JOI21_ho_t4) |
C++17 |
|
830 ms |
119736 KB |
#include <bits/stdc++.h>
using namespace std;
#define DEBUG(x) //x
#define A(x) DEBUG(assert(x))
#define PRINT(x) DEBUG(cerr << x)
#define PV(x) DEBUG(cerr << #x << " = " << x << endl)
#define PAR(x) DEBUG(PRINT(#x << " = { "); for (auto y : x) PRINT(y << ' '); PRINT("}\n");)
#define PAR2(x) DEBUG(PRINT(#x << " = { "); for (auto [y, z] : x) PRINT(y << ',' << z << " "); PRINT("}\n");)
typedef int64_t i64;
const i64 INF = i64(1e18); //1000000007; //998244353;
struct S {
int n, m;
vector<unordered_map<i64, set<pair<i64, i64>>>> edges;
vector<unordered_map<i64, i64>> csum;
void run() {
cin >> n >> m;
edges.resize(n);
csum.resize(n);
for (int i = 0; i < m; ++i) {
i64 a, b, c, p;
cin >> a >> b >> c >> p;
--a; --b;
edges[a][c].insert({b, p});
edges[b][c].insert({a, p});
csum[a][c] += p;
csum[b][c] += p;
}
vector<i64> d(n, INF);
vector<unordered_map<i64, i64>> d2(n);
d[0] = 0;
priority_queue<array<i64, 3>> q;
q.push({0, 0, 0});
while (!q.empty()) {
PAR(q.top());
i64 dist = -q.top()[0];
i64 node = q.top()[1];
i64 c = q.top()[2];
q.pop();
if (c) {
if (d2[node][c] != dist) continue;
for (auto [next, wt] : edges[node][c]) {
i64 rest = d2[node][c] + csum[node][c] - wt;
if (rest < d[next]) {
d[next] = rest;
q.push({-rest, next, 0});
}
}
} else {
if (d[node] != dist) continue;
for (auto &[color, adj] : edges[node]) {
for (auto [next, wt] : adj) {
i64 rest = d[node] + csum[node][color] - wt;
if (rest < d[next]) {
d[next] = rest;
q.push({-rest, next, 0});
}
if (d[node] + wt < d[next]) {
d[next] = d[node] + wt;
q.push({-d[node] - wt, next, 0});
}
if (!d2[next].count(color) || dist < d2[next][color]) {
d2[next][color] = dist;
q.push({-dist, next, color});
}
}
}
}
}
cout << (d[n - 1] >= INF ? -1 : d[n - 1]) << '\n';
}
};
int main() {
ios::sync_with_stdio(0); cin.tie(0);
auto sol = make_unique<S>();
sol->run();
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
1492 KB |
Output is correct |
10 |
Correct |
3 ms |
1364 KB |
Output is correct |
11 |
Correct |
3 ms |
1236 KB |
Output is correct |
12 |
Correct |
3 ms |
1108 KB |
Output is correct |
13 |
Correct |
4 ms |
1236 KB |
Output is correct |
14 |
Correct |
3 ms |
1236 KB |
Output is correct |
15 |
Correct |
2 ms |
980 KB |
Output is correct |
16 |
Correct |
3 ms |
1108 KB |
Output is correct |
17 |
Correct |
3 ms |
980 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
2 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
243 ms |
33340 KB |
Output is correct |
2 |
Correct |
104 ms |
18052 KB |
Output is correct |
3 |
Correct |
370 ms |
31364 KB |
Output is correct |
4 |
Correct |
144 ms |
26116 KB |
Output is correct |
5 |
Correct |
830 ms |
119060 KB |
Output is correct |
6 |
Correct |
688 ms |
109164 KB |
Output is correct |
7 |
Correct |
638 ms |
99988 KB |
Output is correct |
8 |
Correct |
512 ms |
89584 KB |
Output is correct |
9 |
Correct |
539 ms |
89508 KB |
Output is correct |
10 |
Correct |
398 ms |
58624 KB |
Output is correct |
11 |
Correct |
187 ms |
51672 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
0 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
1 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
3 ms |
1492 KB |
Output is correct |
10 |
Correct |
3 ms |
1364 KB |
Output is correct |
11 |
Correct |
3 ms |
1236 KB |
Output is correct |
12 |
Correct |
3 ms |
1108 KB |
Output is correct |
13 |
Correct |
4 ms |
1236 KB |
Output is correct |
14 |
Correct |
3 ms |
1236 KB |
Output is correct |
15 |
Correct |
2 ms |
980 KB |
Output is correct |
16 |
Correct |
3 ms |
1108 KB |
Output is correct |
17 |
Correct |
3 ms |
980 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
2 ms |
596 KB |
Output is correct |
20 |
Correct |
3 ms |
1108 KB |
Output is correct |
21 |
Correct |
243 ms |
33340 KB |
Output is correct |
22 |
Correct |
104 ms |
18052 KB |
Output is correct |
23 |
Correct |
370 ms |
31364 KB |
Output is correct |
24 |
Correct |
144 ms |
26116 KB |
Output is correct |
25 |
Correct |
830 ms |
119060 KB |
Output is correct |
26 |
Correct |
688 ms |
109164 KB |
Output is correct |
27 |
Correct |
638 ms |
99988 KB |
Output is correct |
28 |
Correct |
512 ms |
89584 KB |
Output is correct |
29 |
Correct |
539 ms |
89508 KB |
Output is correct |
30 |
Correct |
398 ms |
58624 KB |
Output is correct |
31 |
Correct |
187 ms |
51672 KB |
Output is correct |
32 |
Correct |
353 ms |
22036 KB |
Output is correct |
33 |
Correct |
266 ms |
30472 KB |
Output is correct |
34 |
Correct |
492 ms |
56748 KB |
Output is correct |
35 |
Correct |
372 ms |
49180 KB |
Output is correct |
36 |
Correct |
440 ms |
82456 KB |
Output is correct |
37 |
Correct |
555 ms |
88500 KB |
Output is correct |
38 |
Correct |
639 ms |
99164 KB |
Output is correct |
39 |
Correct |
460 ms |
30868 KB |
Output is correct |
40 |
Correct |
546 ms |
89552 KB |
Output is correct |
41 |
Correct |
588 ms |
89600 KB |
Output is correct |
42 |
Correct |
587 ms |
89724 KB |
Output is correct |
43 |
Correct |
265 ms |
33792 KB |
Output is correct |
44 |
Correct |
522 ms |
39712 KB |
Output is correct |
45 |
Correct |
440 ms |
83364 KB |
Output is correct |
46 |
Correct |
380 ms |
81228 KB |
Output is correct |
47 |
Correct |
506 ms |
86756 KB |
Output is correct |
48 |
Correct |
799 ms |
119736 KB |
Output is correct |