結果
問題 | 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 |
コンパイル時間 | 1,051 ms |
コンパイル使用メモリ | 89,208 KB |
実行使用メモリ | 15,904 KB |
最終ジャッジ日時 | 2024-09-13 00:53:20 |
合計ジャッジ時間 | 9,502 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,816 KB |
testcase_01 | AC | 2 ms
6,940 KB |
testcase_02 | WA | - |
testcase_03 | AC | 166 ms
12,276 KB |
testcase_04 | AC | 240 ms
15,708 KB |
testcase_05 | AC | 176 ms
12,596 KB |
testcase_06 | AC | 214 ms
14,468 KB |
testcase_07 | AC | 206 ms
13,828 KB |
testcase_08 | AC | 166 ms
12,240 KB |
testcase_09 | AC | 211 ms
14,060 KB |
testcase_10 | WA | - |
testcase_11 | AC | 218 ms
14,572 KB |
testcase_12 | AC | 231 ms
14,776 KB |
testcase_13 | AC | 201 ms
13,660 KB |
testcase_14 | AC | 194 ms
13,684 KB |
testcase_15 | AC | 202 ms
13,532 KB |
testcase_16 | AC | 249 ms
15,904 KB |
testcase_17 | AC | 210 ms
14,276 KB |
testcase_18 | AC | 192 ms
13,336 KB |
testcase_19 | AC | 219 ms
14,728 KB |
testcase_20 | AC | 214 ms
14,672 KB |
testcase_21 | AC | 208 ms
14,072 KB |
testcase_22 | AC | 249 ms
14,888 KB |
testcase_23 | AC | 215 ms
14,072 KB |
testcase_24 | AC | 223 ms
14,592 KB |
testcase_25 | AC | 228 ms
15,448 KB |
testcase_26 | AC | 218 ms
13,980 KB |
testcase_27 | AC | 220 ms
14,484 KB |
testcase_28 | AC | 177 ms
12,844 KB |
testcase_29 | WA | - |
testcase_30 | AC | 225 ms
14,964 KB |
testcase_31 | AC | 239 ms
15,292 KB |
testcase_32 | WA | - |
testcase_33 | WA | - |
testcase_34 | AC | 205 ms
15,352 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; }