# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
494875 |
2021-12-17T05:24:22 Z |
leu_naut |
Robot (JOI21_ho_t4) |
C++11 |
|
971 ms |
87452 KB |
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define FOR(i,a,b) for (int i = a; i <= b; ++i)
#define f first
#define s second
#define FastIO ios_base::sync_with_stdio(0); cin.tie(0);
#define ii pair <int,int>
#define pii pair <ll,ll>
#define all(x) x.begin(),x.end()
const int N = 1e5;
const ll oo = 1e18;
struct Edge
{
int v; ll p;
int tp;
};
map <int, vector <Edge>> g[N + 5];
map <int,ll> dp2[N + 5], psum[N + 5];
ll dp[N + 5];
int main()
{
FastIO
int n,m;
cin >> n >> m;
FOR(i,1,m)
{
int a,b,c,p;
cin >> a >> b >> c >> p;
g[a][c].push_back({b,p,c});
g[b][c].push_back({a,p,c});
psum[a][c] += p;
psum[b][c] += p;
}
FOR(i,1,n) dp[i] = oo;
dp[1] = 0;
priority_queue <tuple <ll, int , int>> q;
q.push({0,1,0});
while (!q.empty()) {
ll cost, node, c;
tie(cost, node, c) = q.top();
q.pop();
if (c) {
for (Edge j : g[node][c]) {
ll case1 = psum[node][c] - j.p - cost;
if (case1 < dp[j.v]) {
dp[j.v] = case1;
q.push({-dp[j.v], j.v, 0});
}
}
}
else {
if (dp[node] != -cost) continue;
for (auto i : g[node]) {
for (Edge j : i.s) {
// Don't pick j, change j's neighbour.
ll case1 = psum[node][j.tp] - j.p - cost;
if (case1 < dp[j.v]) {
dp[j.v] = case1;
q.push({-dp[j.v], j.v, 0});
}
// Pick j & not change its neighbor.
ll case2 = j.p - cost;
if (case2 < dp[j.v]) {
dp[j.v] = case2;
q.push({-dp[j.v], j.v, 0});
}
// Pick j & change its neighbor.
ll case3 = -cost;
if (!dp2[j.v][j.tp] || case3 < dp2[j.v][j.tp]) {
dp2[j.v][j.tp] = case3;
q.push({-dp2[j.v][j.tp], j.v, j.tp});
}
}
}
}
}
if (dp[n] != oo) cout << dp[n];
else cout << -1;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14540 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
7 ms |
14412 KB |
Output is correct |
4 |
Correct |
8 ms |
14392 KB |
Output is correct |
5 |
Correct |
7 ms |
14416 KB |
Output is correct |
6 |
Correct |
8 ms |
14416 KB |
Output is correct |
7 |
Correct |
9 ms |
14544 KB |
Output is correct |
8 |
Correct |
8 ms |
14416 KB |
Output is correct |
9 |
Correct |
14 ms |
15104 KB |
Output is correct |
10 |
Correct |
11 ms |
15020 KB |
Output is correct |
11 |
Correct |
12 ms |
14788 KB |
Output is correct |
12 |
Correct |
10 ms |
14816 KB |
Output is correct |
13 |
Correct |
9 ms |
14800 KB |
Output is correct |
14 |
Correct |
9 ms |
14812 KB |
Output is correct |
15 |
Correct |
8 ms |
14672 KB |
Output is correct |
16 |
Correct |
10 ms |
14800 KB |
Output is correct |
17 |
Correct |
9 ms |
14804 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
9 ms |
14672 KB |
Output is correct |
20 |
Correct |
8 ms |
14676 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
178 ms |
35784 KB |
Output is correct |
2 |
Correct |
74 ms |
25024 KB |
Output is correct |
3 |
Correct |
203 ms |
34284 KB |
Output is correct |
4 |
Correct |
132 ms |
28604 KB |
Output is correct |
5 |
Correct |
920 ms |
85780 KB |
Output is correct |
6 |
Correct |
682 ms |
76032 KB |
Output is correct |
7 |
Correct |
318 ms |
61776 KB |
Output is correct |
8 |
Correct |
396 ms |
54400 KB |
Output is correct |
9 |
Correct |
392 ms |
54316 KB |
Output is correct |
10 |
Correct |
304 ms |
49436 KB |
Output is correct |
11 |
Correct |
128 ms |
34352 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
14540 KB |
Output is correct |
2 |
Correct |
8 ms |
14420 KB |
Output is correct |
3 |
Correct |
7 ms |
14412 KB |
Output is correct |
4 |
Correct |
8 ms |
14392 KB |
Output is correct |
5 |
Correct |
7 ms |
14416 KB |
Output is correct |
6 |
Correct |
8 ms |
14416 KB |
Output is correct |
7 |
Correct |
9 ms |
14544 KB |
Output is correct |
8 |
Correct |
8 ms |
14416 KB |
Output is correct |
9 |
Correct |
14 ms |
15104 KB |
Output is correct |
10 |
Correct |
11 ms |
15020 KB |
Output is correct |
11 |
Correct |
12 ms |
14788 KB |
Output is correct |
12 |
Correct |
10 ms |
14816 KB |
Output is correct |
13 |
Correct |
9 ms |
14800 KB |
Output is correct |
14 |
Correct |
9 ms |
14812 KB |
Output is correct |
15 |
Correct |
8 ms |
14672 KB |
Output is correct |
16 |
Correct |
10 ms |
14800 KB |
Output is correct |
17 |
Correct |
9 ms |
14804 KB |
Output is correct |
18 |
Correct |
8 ms |
14548 KB |
Output is correct |
19 |
Correct |
9 ms |
14672 KB |
Output is correct |
20 |
Correct |
8 ms |
14676 KB |
Output is correct |
21 |
Correct |
178 ms |
35784 KB |
Output is correct |
22 |
Correct |
74 ms |
25024 KB |
Output is correct |
23 |
Correct |
203 ms |
34284 KB |
Output is correct |
24 |
Correct |
132 ms |
28604 KB |
Output is correct |
25 |
Correct |
920 ms |
85780 KB |
Output is correct |
26 |
Correct |
682 ms |
76032 KB |
Output is correct |
27 |
Correct |
318 ms |
61776 KB |
Output is correct |
28 |
Correct |
396 ms |
54400 KB |
Output is correct |
29 |
Correct |
392 ms |
54316 KB |
Output is correct |
30 |
Correct |
304 ms |
49436 KB |
Output is correct |
31 |
Correct |
128 ms |
34352 KB |
Output is correct |
32 |
Correct |
127 ms |
32276 KB |
Output is correct |
33 |
Correct |
148 ms |
31964 KB |
Output is correct |
34 |
Correct |
376 ms |
52512 KB |
Output is correct |
35 |
Correct |
271 ms |
43316 KB |
Output is correct |
36 |
Correct |
286 ms |
49508 KB |
Output is correct |
37 |
Correct |
340 ms |
53456 KB |
Output is correct |
38 |
Correct |
302 ms |
61124 KB |
Output is correct |
39 |
Correct |
144 ms |
36544 KB |
Output is correct |
40 |
Correct |
381 ms |
55532 KB |
Output is correct |
41 |
Correct |
426 ms |
55752 KB |
Output is correct |
42 |
Correct |
462 ms |
63504 KB |
Output is correct |
43 |
Correct |
205 ms |
38460 KB |
Output is correct |
44 |
Correct |
418 ms |
46836 KB |
Output is correct |
45 |
Correct |
297 ms |
50140 KB |
Output is correct |
46 |
Correct |
262 ms |
50212 KB |
Output is correct |
47 |
Correct |
301 ms |
52616 KB |
Output is correct |
48 |
Correct |
971 ms |
87452 KB |
Output is correct |