# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
476848 |
2021-09-28T16:24:41 Z |
tranxuanbach |
Robot (JOI21_ho_t4) |
C++17 |
|
987 ms |
109780 KB |
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (int i = l; i < r; i++)
#define ForE(i, l, r) for (int i = l; i <= r; i++)
#define FordE(i, l, r) for (int i = l; i >= r; i--)
#define Fora(v, a) for (auto v: a)
#define bend(a) a.begin(), a.end()
#define isz(a) ((signed)a.size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
const int N = 1e5 + 5, M = 2e5 + 5;
struct Edge{
int u, v, c, p;
Edge(){
}
Edge(int u, int v, int c, int p): u(u), v(v), c(c), p(p){
}
};
int n, m;
Edge edges[2 * M];
vi adj[N];
unordered_map <int, vi> mppc[N];
unordered_map <int, ll> mppsp[N];
unordered_map <int, ll> distc[N];
ll dist[N];
priority_queue <tuple <ll, int, int>, vector <tuple <ll, int, int>>, greater <tuple <ll, int, int>>> pq;
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("KEK.inp", "r", stdin);
// freopen("KEK.out", "w", stdout);
cin >> n >> m;
ForE(i, 1, m){
int u, v, c, p; cin >> u >> v >> c >> p;
edges[2 * i - 1] = Edge(u, v, c, p);
edges[2 * i] = Edge(v, u, c, p);
adj[u].emplace_back(2 * i - 1);
adj[v].emplace_back(2 * i);
}
memset(dist, 0x3f, sizeof(dist));
ForE(i, 1, 2 * m){
mppc[edges[i].u][edges[i].c].emplace_back(i);
mppsp[edges[i].u][edges[i].c] += edges[i].p;
distc[edges[i].u][edges[i].c] = dist[0];
}
dist[1] = 0; pq.emplace(dist[1], 1, 0);
while (!pq.empty()){
ll d; int u, c; tie(d, u, c) = pq.top(); pq.pop();
if (!c){
if (d != dist[u]){
continue;
}
Fora(elem, mppc[u]){
if (isz(elem.se) == 1){
int i = elem.se[0];
if (dist[edges[i].v] > d){
dist[edges[i].v] = d;
pq.emplace(dist[edges[i].v], edges[i].v, 0);
}
}
Fora(i, elem.se){
if (dist[edges[i].v] > d + edges[i].p){
dist[edges[i].v] = d + edges[i].p;
pq.emplace(dist[edges[i].v], edges[i].v, 0);
}
if (distc[edges[i].v][edges[i].c] > d){
distc[edges[i].v][edges[i].c] = d;
pq.emplace(d, edges[i].v, edges[i].c);
}
}
if (distc[u][elem.fi] > d){
distc[u][elem.fi] = d;
pq.emplace(d, u, elem.fi);
}
}
}
else{
if (d != distc[u][c]){
continue;
}
if (isz(mppc[u][c]) == 1){
continue;
}
Fora(i, mppc[u][c]){
if (dist[edges[i].v] > distc[u][c] + mppsp[u][c] - edges[i].p){
dist[edges[i].v] = distc[u][c] + mppsp[u][c] - edges[i].p;
pq.emplace(dist[edges[i].v], edges[i].v, 0);
}
}
}
}
cout << (dist[n] == dist[0] ? -1 : dist[n]) << endl;
}
/*
==================================================+
INPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT: |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19788 KB |
Output is correct |
2 |
Correct |
11 ms |
19888 KB |
Output is correct |
3 |
Correct |
11 ms |
19788 KB |
Output is correct |
4 |
Correct |
13 ms |
19888 KB |
Output is correct |
5 |
Correct |
11 ms |
19884 KB |
Output is correct |
6 |
Correct |
10 ms |
19888 KB |
Output is correct |
7 |
Correct |
11 ms |
20028 KB |
Output is correct |
8 |
Correct |
12 ms |
19916 KB |
Output is correct |
9 |
Correct |
14 ms |
20716 KB |
Output is correct |
10 |
Correct |
15 ms |
20720 KB |
Output is correct |
11 |
Correct |
14 ms |
20568 KB |
Output is correct |
12 |
Correct |
13 ms |
20412 KB |
Output is correct |
13 |
Correct |
14 ms |
20612 KB |
Output is correct |
14 |
Correct |
14 ms |
20616 KB |
Output is correct |
15 |
Correct |
14 ms |
20408 KB |
Output is correct |
16 |
Correct |
13 ms |
20428 KB |
Output is correct |
17 |
Correct |
13 ms |
20428 KB |
Output is correct |
18 |
Correct |
13 ms |
20300 KB |
Output is correct |
19 |
Correct |
12 ms |
20156 KB |
Output is correct |
20 |
Correct |
14 ms |
20428 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
301 ms |
43080 KB |
Output is correct |
2 |
Correct |
121 ms |
32452 KB |
Output is correct |
3 |
Correct |
336 ms |
39600 KB |
Output is correct |
4 |
Correct |
195 ms |
37952 KB |
Output is correct |
5 |
Correct |
966 ms |
109780 KB |
Output is correct |
6 |
Correct |
872 ms |
97580 KB |
Output is correct |
7 |
Correct |
537 ms |
83464 KB |
Output is correct |
8 |
Correct |
574 ms |
78868 KB |
Output is correct |
9 |
Correct |
675 ms |
78816 KB |
Output is correct |
10 |
Correct |
467 ms |
62836 KB |
Output is correct |
11 |
Correct |
246 ms |
61764 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
19788 KB |
Output is correct |
2 |
Correct |
11 ms |
19888 KB |
Output is correct |
3 |
Correct |
11 ms |
19788 KB |
Output is correct |
4 |
Correct |
13 ms |
19888 KB |
Output is correct |
5 |
Correct |
11 ms |
19884 KB |
Output is correct |
6 |
Correct |
10 ms |
19888 KB |
Output is correct |
7 |
Correct |
11 ms |
20028 KB |
Output is correct |
8 |
Correct |
12 ms |
19916 KB |
Output is correct |
9 |
Correct |
14 ms |
20716 KB |
Output is correct |
10 |
Correct |
15 ms |
20720 KB |
Output is correct |
11 |
Correct |
14 ms |
20568 KB |
Output is correct |
12 |
Correct |
13 ms |
20412 KB |
Output is correct |
13 |
Correct |
14 ms |
20612 KB |
Output is correct |
14 |
Correct |
14 ms |
20616 KB |
Output is correct |
15 |
Correct |
14 ms |
20408 KB |
Output is correct |
16 |
Correct |
13 ms |
20428 KB |
Output is correct |
17 |
Correct |
13 ms |
20428 KB |
Output is correct |
18 |
Correct |
13 ms |
20300 KB |
Output is correct |
19 |
Correct |
12 ms |
20156 KB |
Output is correct |
20 |
Correct |
14 ms |
20428 KB |
Output is correct |
21 |
Correct |
301 ms |
43080 KB |
Output is correct |
22 |
Correct |
121 ms |
32452 KB |
Output is correct |
23 |
Correct |
336 ms |
39600 KB |
Output is correct |
24 |
Correct |
195 ms |
37952 KB |
Output is correct |
25 |
Correct |
966 ms |
109780 KB |
Output is correct |
26 |
Correct |
872 ms |
97580 KB |
Output is correct |
27 |
Correct |
537 ms |
83464 KB |
Output is correct |
28 |
Correct |
574 ms |
78868 KB |
Output is correct |
29 |
Correct |
675 ms |
78816 KB |
Output is correct |
30 |
Correct |
467 ms |
62836 KB |
Output is correct |
31 |
Correct |
246 ms |
61764 KB |
Output is correct |
32 |
Correct |
174 ms |
31124 KB |
Output is correct |
33 |
Correct |
259 ms |
38844 KB |
Output is correct |
34 |
Correct |
544 ms |
58732 KB |
Output is correct |
35 |
Correct |
441 ms |
53176 KB |
Output is correct |
36 |
Correct |
449 ms |
75692 KB |
Output is correct |
37 |
Correct |
589 ms |
78968 KB |
Output is correct |
38 |
Correct |
523 ms |
86736 KB |
Output is correct |
39 |
Correct |
226 ms |
36532 KB |
Output is correct |
40 |
Correct |
581 ms |
78232 KB |
Output is correct |
41 |
Correct |
639 ms |
78404 KB |
Output is correct |
42 |
Correct |
726 ms |
83736 KB |
Output is correct |
43 |
Correct |
301 ms |
44092 KB |
Output is correct |
44 |
Correct |
490 ms |
44072 KB |
Output is correct |
45 |
Correct |
542 ms |
75468 KB |
Output is correct |
46 |
Correct |
457 ms |
74420 KB |
Output is correct |
47 |
Correct |
504 ms |
77992 KB |
Output is correct |
48 |
Correct |
987 ms |
109260 KB |
Output is correct |