# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
526656 |
2022-02-15T21:12:24 Z |
Lobo |
Robot (JOI21_ho_t4) |
C++17 |
|
1040 ms |
120112 KB |
#include<bits/stdc++.h>
using namespace std;
vector<pair<long long,pair<long long,long long>>> g[220000];
map<long long,vector<pair<long long,long long>>> gc[220000];
map<long long,long long> d[220000], sm[220000];
int32_t main() {
long long n, m; cin >> n >> m;
for(long long i = 1; i <= m; i++) {
long long u, v, c, w; cin >> u >> v >> c >> w;
g[u].push_back(make_pair(v,make_pair(c,w)));
g[v].push_back(make_pair(u,make_pair(c,w)));
}
for(long long i = 1; i <= n; i++) {
d[i][0] = 1000000000000000010;
for(auto V : g[i]) {
d[i][V.second.first] = 1000000000000000010;
gc[i][V.second.first].push_back(make_pair(V.first,V.second.second));
sm[i][V.second.first]+= V.second.second;
}
}
priority_queue<pair<long long,pair<long long,long long>>> pq;
pq.push(make_pair(0,make_pair(1,0))); d[1][0] = 0;
while(pq.size()) {
long long u = pq.top().second.first;
long long dist = -pq.top().first;
long long cl = pq.top().second.second;
pq.pop();
if(dist != d[u][cl]) continue;
if(cl == 0) {
for(auto V : g[u]) {
long long v = V.first;
long long c = V.second.first;
long long w = V.second.second;
if(d[v][c] > d[u][0]) {
d[v][c] = d[u][0];
pq.push(make_pair(-d[v][c],make_pair(v,c)));
}
if(d[v][0] > d[u][0] + min(sm[u][c]-w,w)) {
d[v][0] = d[u][0] + min(sm[u][c]-w,w);
pq.push(make_pair(-d[v][0],make_pair(v,0)));
}
}
}
else {
for(auto V : gc[u][cl]) {
long long v = V.first;
long long w = V.second;
long long c = cl;
if(d[v][0] > d[u][c] + sm[u][c] - w) {
d[v][0] = d[u][c] + sm[u][c] - w;
pq.push(make_pair(-d[v][0],make_pair(v,0)));
}
}
}
}
if(d[n][0] == 1000000000000000010) cout << -1 << endl;
else cout << d[n][0] << endl;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
36428 KB |
Output is correct |
2 |
Correct |
17 ms |
36428 KB |
Output is correct |
3 |
Correct |
19 ms |
36428 KB |
Output is correct |
4 |
Correct |
18 ms |
36420 KB |
Output is correct |
5 |
Correct |
17 ms |
36476 KB |
Output is correct |
6 |
Correct |
19 ms |
36380 KB |
Output is correct |
7 |
Correct |
19 ms |
36600 KB |
Output is correct |
8 |
Correct |
17 ms |
36428 KB |
Output is correct |
9 |
Correct |
21 ms |
37288 KB |
Output is correct |
10 |
Correct |
22 ms |
37104 KB |
Output is correct |
11 |
Correct |
23 ms |
36932 KB |
Output is correct |
12 |
Correct |
20 ms |
36940 KB |
Output is correct |
13 |
Correct |
26 ms |
37088 KB |
Output is correct |
14 |
Correct |
20 ms |
37068 KB |
Output is correct |
15 |
Correct |
19 ms |
36812 KB |
Output is correct |
16 |
Correct |
20 ms |
36908 KB |
Output is correct |
17 |
Correct |
22 ms |
36960 KB |
Output is correct |
18 |
Correct |
21 ms |
36684 KB |
Output is correct |
19 |
Correct |
23 ms |
36860 KB |
Output is correct |
20 |
Correct |
19 ms |
36812 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
229 ms |
62464 KB |
Output is correct |
2 |
Correct |
109 ms |
49764 KB |
Output is correct |
3 |
Correct |
322 ms |
61512 KB |
Output is correct |
4 |
Correct |
151 ms |
53824 KB |
Output is correct |
5 |
Correct |
1018 ms |
120112 KB |
Output is correct |
6 |
Correct |
784 ms |
108992 KB |
Output is correct |
7 |
Correct |
400 ms |
88352 KB |
Output is correct |
8 |
Correct |
541 ms |
86116 KB |
Output is correct |
9 |
Correct |
483 ms |
86216 KB |
Output is correct |
10 |
Correct |
364 ms |
81012 KB |
Output is correct |
11 |
Correct |
177 ms |
68008 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
36428 KB |
Output is correct |
2 |
Correct |
17 ms |
36428 KB |
Output is correct |
3 |
Correct |
19 ms |
36428 KB |
Output is correct |
4 |
Correct |
18 ms |
36420 KB |
Output is correct |
5 |
Correct |
17 ms |
36476 KB |
Output is correct |
6 |
Correct |
19 ms |
36380 KB |
Output is correct |
7 |
Correct |
19 ms |
36600 KB |
Output is correct |
8 |
Correct |
17 ms |
36428 KB |
Output is correct |
9 |
Correct |
21 ms |
37288 KB |
Output is correct |
10 |
Correct |
22 ms |
37104 KB |
Output is correct |
11 |
Correct |
23 ms |
36932 KB |
Output is correct |
12 |
Correct |
20 ms |
36940 KB |
Output is correct |
13 |
Correct |
26 ms |
37088 KB |
Output is correct |
14 |
Correct |
20 ms |
37068 KB |
Output is correct |
15 |
Correct |
19 ms |
36812 KB |
Output is correct |
16 |
Correct |
20 ms |
36908 KB |
Output is correct |
17 |
Correct |
22 ms |
36960 KB |
Output is correct |
18 |
Correct |
21 ms |
36684 KB |
Output is correct |
19 |
Correct |
23 ms |
36860 KB |
Output is correct |
20 |
Correct |
19 ms |
36812 KB |
Output is correct |
21 |
Correct |
229 ms |
62464 KB |
Output is correct |
22 |
Correct |
109 ms |
49764 KB |
Output is correct |
23 |
Correct |
322 ms |
61512 KB |
Output is correct |
24 |
Correct |
151 ms |
53824 KB |
Output is correct |
25 |
Correct |
1018 ms |
120112 KB |
Output is correct |
26 |
Correct |
784 ms |
108992 KB |
Output is correct |
27 |
Correct |
400 ms |
88352 KB |
Output is correct |
28 |
Correct |
541 ms |
86116 KB |
Output is correct |
29 |
Correct |
483 ms |
86216 KB |
Output is correct |
30 |
Correct |
364 ms |
81012 KB |
Output is correct |
31 |
Correct |
177 ms |
68008 KB |
Output is correct |
32 |
Correct |
232 ms |
54996 KB |
Output is correct |
33 |
Correct |
230 ms |
58000 KB |
Output is correct |
34 |
Correct |
482 ms |
81296 KB |
Output is correct |
35 |
Correct |
366 ms |
71736 KB |
Output is correct |
36 |
Correct |
342 ms |
78164 KB |
Output is correct |
37 |
Correct |
400 ms |
84076 KB |
Output is correct |
38 |
Correct |
466 ms |
94556 KB |
Output is correct |
39 |
Correct |
283 ms |
61460 KB |
Output is correct |
40 |
Correct |
561 ms |
86136 KB |
Output is correct |
41 |
Correct |
520 ms |
86244 KB |
Output is correct |
42 |
Correct |
584 ms |
98248 KB |
Output is correct |
43 |
Correct |
278 ms |
66104 KB |
Output is correct |
44 |
Correct |
468 ms |
74504 KB |
Output is correct |
45 |
Correct |
411 ms |
80504 KB |
Output is correct |
46 |
Correct |
330 ms |
79344 KB |
Output is correct |
47 |
Correct |
392 ms |
81428 KB |
Output is correct |
48 |
Correct |
1040 ms |
119272 KB |
Output is correct |