# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
838466 |
2023-08-27T05:30:28 Z |
Mathandski |
Robot (JOI21_ho_t4) |
C++17 |
|
931 ms |
85372 KB |
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define is insert
#define ll long long
#define V vector
#define MS multiset
#define PL pair<ll, ll>
#define F first
#define S second
#define PQ priority_queue
#define f0r(i, begin, end) for (ll i = begin; i < end; i ++)
#define For(i, end, begin) for (ll i = end; i > begin; i --)
#define all(x) x.begin(), x.end()
#define INF 1000000000000000000
#define inf 1000000000
#define MOD 1000000007
#define len(x) (ll)x.size()
#define fileread(file) ifstream fin; fin.open((string)file + ".in"); ofstream fout; fout.open((string)file + ".out")
#define fastio ios_base::sync_with_stdio(0LL); cin.tie(nullptr)
template<typename T> istream& operator>>(istream& in, V<T>& a) {for(auto &x : a) in >> x; return in;};
template<typename T> ostream& operator<<(ostream& out, V<T>& a) {for(auto &x : a) out << x << ' '; return out;};
const ll MAX_N = 1e5 + 3 ;
ll N, M;
map<ll, V<PL>> conn[MAX_N];
map<ll, ll> psum[MAX_N];
ll dp[MAX_N];
map<ll, ll> dp2[MAX_N];
int main () {
cin >> N >> M;
f0r (i, 0, M) {
ll a, b, c, d;
cin >> a >> b >> c >> d; a --; b --;
conn[a][c].pb({b, d});
conn[b][c].pb({a, d});
psum[a][c] += d; psum[b][c] += d;
}
f0r (i, 0, N) {
dp[i] = INF;
}
using T = tuple<ll, ll, ll>;
priority_queue<T, vector<T>, greater<T>> pq;
dp[0] = 0;
pq.push({0, 0, -1});
while (pq.size()) {
ll cdist, node, prev;
tie(cdist, node, prev) = pq.top();
pq.pop();
if (prev != -1) {
if (dp2[node][prev] != cdist) continue;
for (auto p : conn[node][prev]) {
ll case1 = psum[node][prev] - p.S + cdist;
if (case1 < dp[p.F]) {
pq.push({dp[p.F] = case1, p.F, -1});
}
}
}
else {
if (cdist != dp[node]) continue;
for (auto i : conn[node]) {
for (auto p : i.S) {
ll case1 = min(psum[node][i.F] - p.S, p.S) + cdist;
if (case1 < dp[p.F]) {
pq.push({dp[p.F] = case1, p.F, -1});
}
ll case2 = cdist;
if (dp2[p.F].find(i.F) == dp2[p.F].end()) {
pq.push({dp2[p.F][i.F] = case2, p.F, i.F});
}
else if (case2 < dp2[p.F][i.F]) {
pq.push({dp2[p.F][i.F] = case2, p.F, i.F});
}
}
}
}
}
if (dp[N - 1] == INF) {
cout << -1 << endl;
}
else {
cout << dp[N - 1] << endl;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
14292 KB |
Output is correct |
2 |
Correct |
7 ms |
14292 KB |
Output is correct |
3 |
Correct |
7 ms |
14292 KB |
Output is correct |
4 |
Correct |
6 ms |
14292 KB |
Output is correct |
5 |
Correct |
6 ms |
14420 KB |
Output is correct |
6 |
Correct |
6 ms |
14412 KB |
Output is correct |
7 |
Correct |
8 ms |
14540 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
10 ms |
15060 KB |
Output is correct |
10 |
Correct |
10 ms |
14920 KB |
Output is correct |
11 |
Correct |
9 ms |
14800 KB |
Output is correct |
12 |
Correct |
9 ms |
14720 KB |
Output is correct |
13 |
Correct |
8 ms |
14804 KB |
Output is correct |
14 |
Correct |
9 ms |
14800 KB |
Output is correct |
15 |
Correct |
9 ms |
14668 KB |
Output is correct |
16 |
Correct |
8 ms |
14676 KB |
Output is correct |
17 |
Correct |
8 ms |
14796 KB |
Output is correct |
18 |
Correct |
7 ms |
14548 KB |
Output is correct |
19 |
Correct |
11 ms |
14664 KB |
Output is correct |
20 |
Correct |
8 ms |
14624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
169 ms |
34576 KB |
Output is correct |
2 |
Correct |
77 ms |
24616 KB |
Output is correct |
3 |
Correct |
189 ms |
31816 KB |
Output is correct |
4 |
Correct |
103 ms |
27792 KB |
Output is correct |
5 |
Correct |
921 ms |
83324 KB |
Output is correct |
6 |
Correct |
711 ms |
72728 KB |
Output is correct |
7 |
Correct |
370 ms |
55092 KB |
Output is correct |
8 |
Correct |
435 ms |
50824 KB |
Output is correct |
9 |
Correct |
455 ms |
50792 KB |
Output is correct |
10 |
Correct |
367 ms |
47956 KB |
Output is correct |
11 |
Correct |
159 ms |
32652 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
14292 KB |
Output is correct |
2 |
Correct |
7 ms |
14292 KB |
Output is correct |
3 |
Correct |
7 ms |
14292 KB |
Output is correct |
4 |
Correct |
6 ms |
14292 KB |
Output is correct |
5 |
Correct |
6 ms |
14420 KB |
Output is correct |
6 |
Correct |
6 ms |
14412 KB |
Output is correct |
7 |
Correct |
8 ms |
14540 KB |
Output is correct |
8 |
Correct |
8 ms |
14420 KB |
Output is correct |
9 |
Correct |
10 ms |
15060 KB |
Output is correct |
10 |
Correct |
10 ms |
14920 KB |
Output is correct |
11 |
Correct |
9 ms |
14800 KB |
Output is correct |
12 |
Correct |
9 ms |
14720 KB |
Output is correct |
13 |
Correct |
8 ms |
14804 KB |
Output is correct |
14 |
Correct |
9 ms |
14800 KB |
Output is correct |
15 |
Correct |
9 ms |
14668 KB |
Output is correct |
16 |
Correct |
8 ms |
14676 KB |
Output is correct |
17 |
Correct |
8 ms |
14796 KB |
Output is correct |
18 |
Correct |
7 ms |
14548 KB |
Output is correct |
19 |
Correct |
11 ms |
14664 KB |
Output is correct |
20 |
Correct |
8 ms |
14624 KB |
Output is correct |
21 |
Correct |
169 ms |
34576 KB |
Output is correct |
22 |
Correct |
77 ms |
24616 KB |
Output is correct |
23 |
Correct |
189 ms |
31816 KB |
Output is correct |
24 |
Correct |
103 ms |
27792 KB |
Output is correct |
25 |
Correct |
921 ms |
83324 KB |
Output is correct |
26 |
Correct |
711 ms |
72728 KB |
Output is correct |
27 |
Correct |
370 ms |
55092 KB |
Output is correct |
28 |
Correct |
435 ms |
50824 KB |
Output is correct |
29 |
Correct |
455 ms |
50792 KB |
Output is correct |
30 |
Correct |
367 ms |
47956 KB |
Output is correct |
31 |
Correct |
159 ms |
32652 KB |
Output is correct |
32 |
Correct |
173 ms |
28584 KB |
Output is correct |
33 |
Correct |
163 ms |
30292 KB |
Output is correct |
34 |
Correct |
467 ms |
50536 KB |
Output is correct |
35 |
Correct |
309 ms |
41816 KB |
Output is correct |
36 |
Correct |
317 ms |
46960 KB |
Output is correct |
37 |
Correct |
389 ms |
50488 KB |
Output is correct |
38 |
Correct |
384 ms |
61352 KB |
Output is correct |
39 |
Correct |
214 ms |
32232 KB |
Output is correct |
40 |
Correct |
451 ms |
52080 KB |
Output is correct |
41 |
Correct |
483 ms |
52332 KB |
Output is correct |
42 |
Correct |
520 ms |
61140 KB |
Output is correct |
43 |
Correct |
232 ms |
37016 KB |
Output is correct |
44 |
Correct |
390 ms |
43048 KB |
Output is correct |
45 |
Correct |
373 ms |
47556 KB |
Output is correct |
46 |
Correct |
323 ms |
48060 KB |
Output is correct |
47 |
Correct |
334 ms |
49884 KB |
Output is correct |
48 |
Correct |
931 ms |
85372 KB |
Output is correct |