| # |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
| 444773 |
2021-07-15T08:11:08 Z |
dutch |
Robot (JOI21_ho_t4) |
C++17 |
|
1358 ms |
89136 KB |
#include <bits/stdc++.h>
#define int int64_t
using namespace std;
const int LIM = 1e5, INF = 1e18;
map<int, int> d[LIM], s[LIM];
map<int, vector<array<int, 2>>> g[LIM];
priority_queue<array<int, 3>> q;
void add(int i, int j, int k){
if(d[i][k] > j) q.push({-(d[i][k] = j), i, k});
}
signed main(){
cin.tie(0)->sync_with_stdio(0);
int n, m; cin >> n >> m;
for(int i=0; i<m; ++i){
int u, v, c, w; cin >> u >> v >> c >> w;
--u, --v;
g[u][c].push_back({v, w});
g[v][c].push_back({u, w});
s[u][c] += w;
s[v][c] += w;
d[u][c] = d[v][c] = INF;
}
for(int u=0; u<n; ++u) d[u][0] = INF;
q.push({d[0][0] = 0, 0});
while(!q.empty()){
int dist = -q.top()[0], u = q.top()[1], c = q.top()[2];
q.pop();
if(dist != d[u][c]) continue;
if(c){
for(auto &[v, w] : g[u][c])
if(s[u][c] - w >= 0)
add(v, dist + s[u][c] - w, 0);
}else{
for(auto &h : g[u])
for(auto &[v, w] : h.second){
add(v, dist + w, 0);
add(v, dist + s[u][h.first] - w, 0);
add(v, dist, h.first);
}
}
}
cout << (d[n-1][0] == INF ? -1 : d[n-1][0]);
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14312 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 7 |
Correct |
10 ms |
14588 KB |
Output is correct |
| 8 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 9 |
Correct |
13 ms |
15060 KB |
Output is correct |
| 10 |
Correct |
12 ms |
14924 KB |
Output is correct |
| 11 |
Correct |
10 ms |
14868 KB |
Output is correct |
| 12 |
Correct |
10 ms |
14788 KB |
Output is correct |
| 13 |
Correct |
10 ms |
14908 KB |
Output is correct |
| 14 |
Correct |
11 ms |
14924 KB |
Output is correct |
| 15 |
Correct |
10 ms |
14668 KB |
Output is correct |
| 16 |
Correct |
11 ms |
14796 KB |
Output is correct |
| 17 |
Correct |
10 ms |
14796 KB |
Output is correct |
| 18 |
Correct |
10 ms |
14692 KB |
Output is correct |
| 19 |
Correct |
10 ms |
14668 KB |
Output is correct |
| 20 |
Correct |
10 ms |
14668 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
297 ms |
35392 KB |
Output is correct |
| 2 |
Correct |
114 ms |
25408 KB |
Output is correct |
| 3 |
Correct |
296 ms |
30980 KB |
Output is correct |
| 4 |
Correct |
174 ms |
28484 KB |
Output is correct |
| 5 |
Correct |
1332 ms |
89136 KB |
Output is correct |
| 6 |
Correct |
996 ms |
75764 KB |
Output is correct |
| 7 |
Correct |
488 ms |
58012 KB |
Output is correct |
| 8 |
Correct |
511 ms |
52372 KB |
Output is correct |
| 9 |
Correct |
538 ms |
52360 KB |
Output is correct |
| 10 |
Correct |
461 ms |
51132 KB |
Output is correct |
| 11 |
Correct |
179 ms |
40000 KB |
Output is correct |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 2 |
Correct |
8 ms |
14312 KB |
Output is correct |
| 3 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 4 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 5 |
Correct |
8 ms |
14412 KB |
Output is correct |
| 6 |
Correct |
8 ms |
14284 KB |
Output is correct |
| 7 |
Correct |
10 ms |
14588 KB |
Output is correct |
| 8 |
Correct |
9 ms |
14412 KB |
Output is correct |
| 9 |
Correct |
13 ms |
15060 KB |
Output is correct |
| 10 |
Correct |
12 ms |
14924 KB |
Output is correct |
| 11 |
Correct |
10 ms |
14868 KB |
Output is correct |
| 12 |
Correct |
10 ms |
14788 KB |
Output is correct |
| 13 |
Correct |
10 ms |
14908 KB |
Output is correct |
| 14 |
Correct |
11 ms |
14924 KB |
Output is correct |
| 15 |
Correct |
10 ms |
14668 KB |
Output is correct |
| 16 |
Correct |
11 ms |
14796 KB |
Output is correct |
| 17 |
Correct |
10 ms |
14796 KB |
Output is correct |
| 18 |
Correct |
10 ms |
14692 KB |
Output is correct |
| 19 |
Correct |
10 ms |
14668 KB |
Output is correct |
| 20 |
Correct |
10 ms |
14668 KB |
Output is correct |
| 21 |
Correct |
297 ms |
35392 KB |
Output is correct |
| 22 |
Correct |
114 ms |
25408 KB |
Output is correct |
| 23 |
Correct |
296 ms |
30980 KB |
Output is correct |
| 24 |
Correct |
174 ms |
28484 KB |
Output is correct |
| 25 |
Correct |
1332 ms |
89136 KB |
Output is correct |
| 26 |
Correct |
996 ms |
75764 KB |
Output is correct |
| 27 |
Correct |
488 ms |
58012 KB |
Output is correct |
| 28 |
Correct |
511 ms |
52372 KB |
Output is correct |
| 29 |
Correct |
538 ms |
52360 KB |
Output is correct |
| 30 |
Correct |
461 ms |
51132 KB |
Output is correct |
| 31 |
Correct |
179 ms |
40000 KB |
Output is correct |
| 32 |
Correct |
182 ms |
25584 KB |
Output is correct |
| 33 |
Correct |
223 ms |
28924 KB |
Output is correct |
| 34 |
Correct |
627 ms |
50404 KB |
Output is correct |
| 35 |
Correct |
431 ms |
42552 KB |
Output is correct |
| 36 |
Correct |
424 ms |
50096 KB |
Output is correct |
| 37 |
Correct |
479 ms |
53896 KB |
Output is correct |
| 38 |
Correct |
536 ms |
64188 KB |
Output is correct |
| 39 |
Correct |
189 ms |
28152 KB |
Output is correct |
| 40 |
Correct |
527 ms |
52344 KB |
Output is correct |
| 41 |
Correct |
578 ms |
52420 KB |
Output is correct |
| 42 |
Correct |
691 ms |
64864 KB |
Output is correct |
| 43 |
Correct |
306 ms |
38720 KB |
Output is correct |
| 44 |
Correct |
621 ms |
39488 KB |
Output is correct |
| 45 |
Correct |
422 ms |
49032 KB |
Output is correct |
| 46 |
Correct |
366 ms |
49736 KB |
Output is correct |
| 47 |
Correct |
476 ms |
52628 KB |
Output is correct |
| 48 |
Correct |
1358 ms |
89004 KB |
Output is correct |
