# |
Submission time |
Handle |
Problem |
Language |
Result |
Execution time |
Memory |
753452 |
2023-06-05T08:43:29 Z |
PanosPask |
Robot (JOI21_ho_t4) |
C++14 |
|
1183 ms |
123276 KB |
#include <bits/stdc++.h>
#define pb push_back
#define mp make_pair
#define f first
#define s second
using namespace std;
typedef long long ll;
typedef pair<int, int> pi;
typedef pair<ll, int> pli;
typedef pair<ll, pi> plp;
struct Edge {
int dest;
int colour;
int price;
};
int n, m;
vector<map<int, ll>> colourcost;
vector<map<int, bool>> visited;
vector<map<int, ll>> dist;
vector<map<int, vector<Edge>>> by_colour;
vector<vector<Edge>> adj_list;
int main(void)
{
scanf("%d %d", &n, &m);
adj_list.resize(n);
colourcost.resize(n);
dist.resize(n);
by_colour.resize(n);
visited.resize(n);
for (int i = 0; i < m; i++) {
int u, v, c, p;
scanf("%d %d %d %d", &u, &v, &c, &p);
u--; v--;
colourcost[u][c] += p;
by_colour[u][0].pb({v, c, p});
by_colour[u][c].pb({v, c, p});
colourcost[v][c] += p;
by_colour[v][0].pb({u, c, p});
by_colour[v][c].pb({u, c, p});
}
priority_queue<plp, vector<plp>, greater<plp>> q;
dist[0][0] = 0;
q.push(mp(0, mp(0, 0)));
while (!q.empty()) {
int v, c;
tie(v, c) = q.top().s;
q.pop();
if (visited[v][c])
continue;
visited[v][c] = true;
for (auto e : by_colour[v][c]) {
ll current_cost = colourcost[v][e.colour] - e.price;
//Add normally first, by colour later
if (c == 0)
current_cost = min(current_cost, (ll)e.price);
if ((dist[e.dest].find(0) == dist[e.dest].end())
|| (dist[e.dest][0] > dist[v][c] + current_cost)) {
dist[e.dest][0] = dist[v][c] + current_cost;
q.push(mp(dist[e.dest][0], mp(e.dest, 0)));
}
if (c == 0) {
// Add by colour only, c has to be equal to 0
// Force next step to be in same colour => The weight of the edge will be counted later
if ((dist[e.dest].find(e.colour) == dist[e.dest].end())
|| (dist[e.dest][e.colour] > dist[v][c])) {
dist[e.dest][e.colour] = dist[v][c];
q.push(mp(dist[e.dest][e.colour], mp(e.dest, e.colour)));
}
}
}
}
if (dist[n - 1].find(0) == dist[n - 1].end()) {
printf("%d\n", -1);
}
else {
ll ans = dist[n - 1][0];
printf("%lld\n", ans);
}
return 0;
}
Compilation message
Main.cpp: In function 'int main()':
Main.cpp:30:10: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
30 | scanf("%d %d", &n, &m);
| ~~~~~^~~~~~~~~~~~~~~~~
Main.cpp:40:14: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
40 | scanf("%d %d %d %d", &u, &v, &c, &p);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
5 ms |
1500 KB |
Output is correct |
10 |
Correct |
5 ms |
1364 KB |
Output is correct |
11 |
Correct |
2 ms |
1084 KB |
Output is correct |
12 |
Correct |
3 ms |
1108 KB |
Output is correct |
13 |
Correct |
3 ms |
1108 KB |
Output is correct |
14 |
Correct |
3 ms |
1108 KB |
Output is correct |
15 |
Correct |
2 ms |
980 KB |
Output is correct |
16 |
Correct |
3 ms |
1108 KB |
Output is correct |
17 |
Correct |
3 ms |
980 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
2 ms |
1108 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
230 ms |
33992 KB |
Output is correct |
2 |
Correct |
95 ms |
18632 KB |
Output is correct |
3 |
Correct |
246 ms |
26464 KB |
Output is correct |
4 |
Correct |
145 ms |
25888 KB |
Output is correct |
5 |
Correct |
1163 ms |
117844 KB |
Output is correct |
6 |
Correct |
963 ms |
103920 KB |
Output is correct |
7 |
Correct |
379 ms |
79356 KB |
Output is correct |
8 |
Correct |
471 ms |
82740 KB |
Output is correct |
9 |
Correct |
482 ms |
82628 KB |
Output is correct |
10 |
Correct |
412 ms |
58480 KB |
Output is correct |
11 |
Correct |
149 ms |
42696 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
0 ms |
212 KB |
Output is correct |
2 |
Correct |
1 ms |
212 KB |
Output is correct |
3 |
Correct |
0 ms |
212 KB |
Output is correct |
4 |
Correct |
0 ms |
212 KB |
Output is correct |
5 |
Correct |
1 ms |
340 KB |
Output is correct |
6 |
Correct |
0 ms |
212 KB |
Output is correct |
7 |
Correct |
2 ms |
468 KB |
Output is correct |
8 |
Correct |
1 ms |
340 KB |
Output is correct |
9 |
Correct |
5 ms |
1500 KB |
Output is correct |
10 |
Correct |
5 ms |
1364 KB |
Output is correct |
11 |
Correct |
2 ms |
1084 KB |
Output is correct |
12 |
Correct |
3 ms |
1108 KB |
Output is correct |
13 |
Correct |
3 ms |
1108 KB |
Output is correct |
14 |
Correct |
3 ms |
1108 KB |
Output is correct |
15 |
Correct |
2 ms |
980 KB |
Output is correct |
16 |
Correct |
3 ms |
1108 KB |
Output is correct |
17 |
Correct |
3 ms |
980 KB |
Output is correct |
18 |
Correct |
1 ms |
724 KB |
Output is correct |
19 |
Correct |
3 ms |
596 KB |
Output is correct |
20 |
Correct |
2 ms |
1108 KB |
Output is correct |
21 |
Correct |
230 ms |
33992 KB |
Output is correct |
22 |
Correct |
95 ms |
18632 KB |
Output is correct |
23 |
Correct |
246 ms |
26464 KB |
Output is correct |
24 |
Correct |
145 ms |
25888 KB |
Output is correct |
25 |
Correct |
1163 ms |
117844 KB |
Output is correct |
26 |
Correct |
963 ms |
103920 KB |
Output is correct |
27 |
Correct |
379 ms |
79356 KB |
Output is correct |
28 |
Correct |
471 ms |
82740 KB |
Output is correct |
29 |
Correct |
482 ms |
82628 KB |
Output is correct |
30 |
Correct |
412 ms |
58480 KB |
Output is correct |
31 |
Correct |
149 ms |
42696 KB |
Output is correct |
32 |
Correct |
161 ms |
18144 KB |
Output is correct |
33 |
Correct |
195 ms |
26812 KB |
Output is correct |
34 |
Correct |
548 ms |
61300 KB |
Output is correct |
35 |
Correct |
403 ms |
50796 KB |
Output is correct |
36 |
Correct |
369 ms |
76340 KB |
Output is correct |
37 |
Correct |
390 ms |
79764 KB |
Output is correct |
38 |
Correct |
407 ms |
84668 KB |
Output is correct |
39 |
Correct |
179 ms |
25372 KB |
Output is correct |
40 |
Correct |
491 ms |
88040 KB |
Output is correct |
41 |
Correct |
526 ms |
88188 KB |
Output is correct |
42 |
Correct |
622 ms |
91188 KB |
Output is correct |
43 |
Correct |
255 ms |
35272 KB |
Output is correct |
44 |
Correct |
545 ms |
40296 KB |
Output is correct |
45 |
Correct |
424 ms |
81836 KB |
Output is correct |
46 |
Correct |
359 ms |
81672 KB |
Output is correct |
47 |
Correct |
378 ms |
78808 KB |
Output is correct |
48 |
Correct |
1183 ms |
123276 KB |
Output is correct |