#include <cstddef>
#include <cstdint>
#include <iostream>
#include <limits>
#include <map>
#include <queue>
#include <utility>
#include <vector>
int main() {
using usize = std::size_t;
using u64 = std::uint64_t;
struct edge_type {
usize to;
u64 cost;
bool operator<(const edge_type &r) const { return cost > r.cost; }
};
std::ios::sync_with_stdio(false);
std::cin.tie(nullptr);
usize N, M;
std::cin >> N >> M;
const usize ext_N = N + 2 * M;
std::vector<std::vector<edge_type>> graph(ext_N);
{
usize next_id = N;
std::map<std::pair<usize, usize>, usize> id_map;
const auto id = [&](const usize v, const usize c) -> usize {
const auto [itr, success] = id_map.insert({{v, c}, next_id});
if (success) {
next_id += 1;
}
return itr->second;
};
std::vector<u64> sum(ext_N, 0);
for (usize i = 0; i != M; i += 1) {
usize A, B, C;
u64 P;
std::cin >> A >> B >> C >> P;
A -= 1;
B -= 1;
for (usize t = 0; t != 2; t += 1) {
std::swap(A, B);
sum[id(A, C)] += P;
graph[A].push_back({B, P});
graph[A].push_back({id(B, C), 0});
graph[id(A, C)].push_back({B, -P});
}
}
for (const auto &[key, u] : id_map) {
const auto &[v, c] = key;
graph[v].push_back({u, 0});
for (edge_type &edge : graph[u]) {
edge.cost += sum[u];
}
}
}
static constexpr u64 Inf = std::numeric_limits<u64>::max();
std::vector<u64> dist(ext_N, Inf);
{
std::priority_queue<edge_type> que;
const auto push = [&](const usize v, const u64 d) -> void {
if (dist[v] > d) {
dist[v] = d;
que.push({v, d});
}
};
push(0, 0);
while (!que.empty()) {
const usize v = que.top().to;
const u64 d = que.top().cost;
que.pop();
if (dist[v] < d) {
continue;
}
for (const edge_type &edge : graph[v]) {
push(edge.to, d + edge.cost);
}
}
}
if (dist[N - 1] == Inf) {
std::cout << "-1\n";
} else {
std::cout << dist[N - 1] << "\n";
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
1100 KB |
Output is correct |
10 |
Correct |
3 ms |
972 KB |
Output is correct |
11 |
Correct |
2 ms |
972 KB |
Output is correct |
12 |
Correct |
4 ms |
844 KB |
Output is correct |
13 |
Correct |
3 ms |
972 KB |
Output is correct |
14 |
Correct |
4 ms |
972 KB |
Output is correct |
15 |
Correct |
2 ms |
716 KB |
Output is correct |
16 |
Correct |
3 ms |
844 KB |
Output is correct |
17 |
Correct |
3 ms |
716 KB |
Output is correct |
18 |
Correct |
2 ms |
460 KB |
Output is correct |
19 |
Correct |
2 ms |
844 KB |
Output is correct |
20 |
Correct |
3 ms |
716 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
222 ms |
26844 KB |
Output is correct |
2 |
Correct |
77 ms |
12532 KB |
Output is correct |
3 |
Correct |
276 ms |
37940 KB |
Output is correct |
4 |
Correct |
131 ms |
17744 KB |
Output is correct |
5 |
Correct |
772 ms |
81124 KB |
Output is correct |
6 |
Correct |
667 ms |
74972 KB |
Output is correct |
7 |
Correct |
446 ms |
66012 KB |
Output is correct |
8 |
Correct |
647 ms |
63636 KB |
Output is correct |
9 |
Correct |
662 ms |
63672 KB |
Output is correct |
10 |
Correct |
421 ms |
42928 KB |
Output is correct |
11 |
Correct |
255 ms |
33368 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
1 ms |
204 KB |
Output is correct |
2 |
Correct |
0 ms |
204 KB |
Output is correct |
3 |
Correct |
0 ms |
204 KB |
Output is correct |
4 |
Correct |
0 ms |
204 KB |
Output is correct |
5 |
Correct |
1 ms |
332 KB |
Output is correct |
6 |
Correct |
0 ms |
204 KB |
Output is correct |
7 |
Correct |
1 ms |
460 KB |
Output is correct |
8 |
Correct |
1 ms |
332 KB |
Output is correct |
9 |
Correct |
3 ms |
1100 KB |
Output is correct |
10 |
Correct |
3 ms |
972 KB |
Output is correct |
11 |
Correct |
2 ms |
972 KB |
Output is correct |
12 |
Correct |
4 ms |
844 KB |
Output is correct |
13 |
Correct |
3 ms |
972 KB |
Output is correct |
14 |
Correct |
4 ms |
972 KB |
Output is correct |
15 |
Correct |
2 ms |
716 KB |
Output is correct |
16 |
Correct |
3 ms |
844 KB |
Output is correct |
17 |
Correct |
3 ms |
716 KB |
Output is correct |
18 |
Correct |
2 ms |
460 KB |
Output is correct |
19 |
Correct |
2 ms |
844 KB |
Output is correct |
20 |
Correct |
3 ms |
716 KB |
Output is correct |
21 |
Correct |
222 ms |
26844 KB |
Output is correct |
22 |
Correct |
77 ms |
12532 KB |
Output is correct |
23 |
Correct |
276 ms |
37940 KB |
Output is correct |
24 |
Correct |
131 ms |
17744 KB |
Output is correct |
25 |
Correct |
772 ms |
81124 KB |
Output is correct |
26 |
Correct |
667 ms |
74972 KB |
Output is correct |
27 |
Correct |
446 ms |
66012 KB |
Output is correct |
28 |
Correct |
647 ms |
63636 KB |
Output is correct |
29 |
Correct |
662 ms |
63672 KB |
Output is correct |
30 |
Correct |
421 ms |
42928 KB |
Output is correct |
31 |
Correct |
255 ms |
33368 KB |
Output is correct |
32 |
Correct |
221 ms |
37152 KB |
Output is correct |
33 |
Correct |
215 ms |
34244 KB |
Output is correct |
34 |
Correct |
466 ms |
49332 KB |
Output is correct |
35 |
Correct |
365 ms |
38788 KB |
Output is correct |
36 |
Correct |
401 ms |
48928 KB |
Output is correct |
37 |
Correct |
418 ms |
57472 KB |
Output is correct |
38 |
Correct |
446 ms |
70944 KB |
Output is correct |
39 |
Correct |
262 ms |
48620 KB |
Output is correct |
40 |
Correct |
662 ms |
64968 KB |
Output is correct |
41 |
Correct |
679 ms |
65068 KB |
Output is correct |
42 |
Correct |
679 ms |
62440 KB |
Output is correct |
43 |
Correct |
268 ms |
32724 KB |
Output is correct |
44 |
Correct |
471 ms |
56664 KB |
Output is correct |
45 |
Correct |
522 ms |
50248 KB |
Output is correct |
46 |
Correct |
455 ms |
46804 KB |
Output is correct |
47 |
Correct |
418 ms |
54068 KB |
Output is correct |
48 |
Correct |
816 ms |
83092 KB |
Output is correct |