結果
問題 | No.1301 Strange Graph Shortest Path |
ユーザー | KoD |
提出日時 | 2020-11-27 21:51:28 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 3,439 bytes |
コンパイル時間 | 949 ms |
コンパイル使用メモリ | 88,700 KB |
実行使用メモリ | 15,592 KB |
最終ジャッジ日時 | 2023-10-10 21:40:16 |
合計ジャッジ時間 | 8,588 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,356 KB |
testcase_01 | AC | 1 ms
4,348 KB |
testcase_02 | WA | - |
testcase_03 | AC | 144 ms
12,196 KB |
testcase_04 | AC | 205 ms
15,332 KB |
testcase_05 | AC | 153 ms
12,516 KB |
testcase_06 | AC | 181 ms
14,400 KB |
testcase_07 | AC | 172 ms
13,620 KB |
testcase_08 | AC | 144 ms
12,244 KB |
testcase_09 | AC | 171 ms
13,724 KB |
testcase_10 | WA | - |
testcase_11 | AC | 183 ms
14,252 KB |
testcase_12 | AC | 184 ms
14,708 KB |
testcase_13 | AC | 171 ms
13,704 KB |
testcase_14 | AC | 170 ms
13,492 KB |
testcase_15 | AC | 167 ms
13,472 KB |
testcase_16 | AC | 196 ms
15,592 KB |
testcase_17 | AC | 185 ms
13,884 KB |
testcase_18 | AC | 166 ms
13,088 KB |
testcase_19 | AC | 185 ms
14,656 KB |
testcase_20 | AC | 181 ms
14,476 KB |
testcase_21 | AC | 176 ms
14,048 KB |
testcase_22 | AC | 190 ms
14,764 KB |
testcase_23 | AC | 177 ms
13,732 KB |
testcase_24 | AC | 188 ms
14,476 KB |
testcase_25 | AC | 199 ms
15,140 KB |
testcase_26 | AC | 174 ms
13,916 KB |
testcase_27 | AC | 185 ms
14,104 KB |
testcase_28 | AC | 155 ms
12,752 KB |
testcase_29 | WA | - |
testcase_30 | AC | 192 ms
14,988 KB |
testcase_31 | AC | 204 ms
15,180 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 174 ms
15,228 KB |
ソースコード
#line 1 "main.cpp" /** * @title Template */ #include <iostream> #include <algorithm> #include <utility> #include <numeric> #include <vector> #include <array> #include <cassert> #include <queue> #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/chmin_chmax.cpp" template <class T, class U> constexpr bool chmin(T &lhs, const U &rhs) { if (lhs > rhs) { lhs = rhs; return true; } return false; } template <class T, class U> constexpr bool chmax(T &lhs, const U &rhs) { if (lhs < rhs) { lhs = rhs; return true; } return false; } /** * @title Chmin/Chmax */ #line 2 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp" #line 4 "/Users/kodamankod/Desktop/cpp_programming/Library/other/range.cpp" class range { struct iter { std::size_t itr; constexpr iter(std::size_t pos) noexcept: itr(pos) { } constexpr void operator ++ () noexcept { ++itr; } constexpr bool operator != (iter other) const noexcept { return itr != other.itr; } constexpr std::size_t operator * () const noexcept { return itr; } }; struct reviter { std::size_t itr; constexpr reviter(std::size_t pos) noexcept: itr(pos) { } constexpr void operator ++ () noexcept { --itr; } constexpr bool operator != (reviter other) const noexcept { return itr != other.itr; } constexpr std::size_t operator * () const noexcept { return itr; } }; const iter first, last; public: constexpr range(std::size_t first, std::size_t last) noexcept: first(first), last(std::max(first, last)) { } constexpr iter begin() const noexcept { return first; } constexpr iter end() const noexcept { return last; } constexpr reviter rbegin() const noexcept { return reviter(*last - 1); } constexpr reviter rend() const noexcept { return reviter(*first - 1); } }; /** * @title Range */ #line 17 "main.cpp" using i32 = std::int32_t; using i64 = std::int64_t; using u32 = std::uint32_t; using u64 = std::uint64_t; using isize = std::ptrdiff_t; using usize = std::size_t; constexpr i32 inf32 = (i32(1) << 30) - 1; constexpr i64 inf64 = (i64(1) << 62) - 1; int main() { usize N, M; std::cin >> N >> M; std::vector<usize> U(M), V(M); std::vector<u64> C(M), D(M); std::vector<std::vector<std::pair<usize, usize>>> graph(N); for (auto i: range(0, M)) { std::cin >> U[i] >> V[i] >> C[i] >> D[i]; U[i] -= 1; V[i] -= 1; graph[U[i]].emplace_back(V[i], i); graph[V[i]].emplace_back(U[i], i); } const auto solve = [&](const usize src, const usize dest) { std::vector<u64> dist(N, inf64); std::vector<usize> last(N, M); std::priority_queue<std::pair<u64, usize>, std::vector<std::pair<u64, usize>>, std::greater<std::pair<u64, usize>>> que; const auto try_push = [&](const usize u, const usize e, const usize d) { if (chmin(dist[u], d)) { last[u] = e; que.emplace(dist[u], u); } }; try_push(src, M, 0); while (!que.empty()) { const auto [d, u] = que.top(); que.pop(); if (dist[u] < d) { continue; } for (const auto [v, e]: graph[u]) { try_push(v, e, d + C[e]); } } usize cur = dest; while (last[cur] != M) { const auto i = last[cur]; cur = (U[i] == cur ? V[i] : U[i]); std::swap(C[i], D[i]); } return dist[dest]; }; u64 ans = 0; ans += solve(0, N - 1); ans += solve(N - 1, 0); std::cout << ans << '\n'; return 0; }