結果
| 問題 | No.859 路線A、路線B、路線C |
| ユーザー |
 Pachicobue
|
| 提出日時 | 2019-08-09 21:43:33 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 2 ms / 1,000 ms |
| コード長 | 8,416 bytes |
| コンパイル時間 | 2,249 ms |
| コンパイル使用メモリ | 208,788 KB |
| 最終ジャッジ日時 | 2025-01-07 11:18:30 |
|
ジャッジサーバーID （参考情報） |
judge2 / judge3 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 12 |
ソースコード
#include <bits/stdc++.h>#pragma GCC diagnostic ignored "-Wsign-compare"#pragma GCC diagnostic ignored "-Wsign-conversion"#define NDEBUG#define SHOW(...) static_cast<void>(0)//!===========================================================!////! dP dP dP !////! 88 88 88 !////! 88aaaaa88a .d8888b. .d8888b. .d888b88 .d8888b. 88d888b. !////! 88 88 88ooood8 88' '88 88' '88 88ooood8 88' '88 !////! 88 88 88. ... 88. .88 88. .88 88. ... 88 !////! dP dP '88888P' '88888P8 '88888P8 '88888P' dP !////!===========================================================!//template <typename T>T read(){T v;return std::cin >> v, v;}template <typename T>std::vector<T> readVec(const std::size_t l){std::vector<T> v(l);for (auto& e : v) { std::cin >> e; }return v;}using ld = long double;using uint = unsigned int;using ll = long long;using ull = unsigned long long;constexpr unsigned int MOD = 1000000007;template <typename T>constexpr T INF = std::numeric_limits<T>::max() / 4;template <typename F>constexpr F PI = static_cast<F>(3.1415926535897932385);std::mt19937 mt{std::random_device{}()};template <typename T>bool chmin(T& a, const T& b) { return (a > b ? a = b, true : false); }template <typename T>bool chmax(T& a, const T& b) { return (a < b ? a = b, true : false); }template <typename T>std::vector<T> Vec(const std::size_t n, T v) { return std::vector<T>(n, v); }template <class... Args>auto Vec(const std::size_t n, Args... args) { return std::vector<decltype(Vec(args...))>(n, Vec(args...)); }template <typename T>constexpr T popCount(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : (T)__builtin_popcountll(u);#elseunsigned long long v = static_cast<unsigned long long>(u);return v = (v & 0x5555555555555555ULL) + (v >> 1 & 0x5555555555555555ULL), v = (v & 0x3333333333333333ULL) + (v >> 2 & 0x3333333333333333ULL), v= (v + (v >> 4)) & 0x0F0F0F0F0F0F0F0FULL, static_cast<T>(v * 0x0101010101010101ULL >> 56 & 0x7f);#endif}template <typename T>constexpr T log2p1(const T u){#ifdef __has_builtinreturn u == 0 ? T(0) : T(64 - __builtin_clzll(u));#elseunsigned long long v = static_cast<unsigned long long>(u);return v = static_cast<unsigned long long>(v), v |= (v >> 1), v |= (v >> 2), v |= (v >> 4), v |= (v >> 8), v |= (v >> 16), v |= (v >> 32),popCount(v);#endif}template <typename T>constexpr T clog(const T v) { return v == 0 ? T(0) : log2p1(v - 1); }template <typename T>constexpr T msbp1(const T v) { return log2p1(v); }template <typename T>constexpr T lsbp1(const T v){#ifdef __has_builtinreturn __builtin_ffsll(v);#elsereturn v == 0 ? T(0) : popCount((v & (-v)) - T(1)) + T(1);#endif}template <typename T>constexpr bool ispow2(const T v) { return popCount(v) == 1; }template <typename T>constexpr T ceil2(const T v) { return v == 0 ? T(1) : T(1) << log2p1(v - 1); }template <typename T>constexpr T floor2(const T v) { return v == 0 ? T(0) : T(1) << (log2p1(v) - 1); }//!=================================================!////! .88888. dP !////! d8' '88 88 !////! 88 88d888b. .d8888b. 88d888b. 88d888b. !////! 88 YP88 88' '88 88' '88 88' '88 88' '88 !////! Y8. .88 88 88. .88 88. .88 88 88 !////! '88888' dP '88888P8 88Y888P' dP dP !////! 88 !////! dP !////!=================================================!//template <typename Cost>struct BaseGraph{BaseGraph(const std::size_t v) : V{v}, edge(v), rev_edge(v) {}void addEdge(const std::size_t from, const std::size_t to, const Cost cost, const bool bi = false){assert(from < V), assert(to < V);edge[from].push_back(Edge{to, cost}), rev_edge[to].push_back(Edge(from, cost));if (bi) { addEdge(to, from, cost, false); }}struct Edge{Edge(const std::size_t to, const Cost cost) : to{to}, cost{cost} {}const std::size_t to;const Cost cost;bool operator<(const Edge& e) const { return cost != e.cost ? cost < e.cost : to < e.to; }};const std::vector<Edge>& operator[](const std::size_t i) const { return assert(i < V), edge[i]; }friend std::ostream& operator<<(std::ostream& os, const BaseGraph& g){os << "[\n";for (std::size_t i = 0; i < g.V; i++) {for (const auto& e : g.edge[i]) { os << i << "->" << e.to << ":" << e.cost << "\n"; }}return (os << "]\n");}static std::size_t to(const Edge& e) { return e.to; }const std::size_t V;std::vector<std::vector<Edge>> edge, rev_edge;};template <>struct BaseGraph<void>{BaseGraph(const std::size_t v) : V{v}, edge(v), rev_edge(v) {}void addEdge(const std::size_t from, const std::size_t to, const bool bi = false){assert(from < V), assert(to < V);edge[from].push_back(to), rev_edge[to].push_back(from);if (bi) { addEdge(to, from, false); }}const std::vector<std::size_t>& operator[](const std::size_t i) const { return assert(i < V), edge[i]; }friend std::ostream& operator<<(std::ostream& os, const BaseGraph& g){os << "[\n";for (std::size_t i = 0; i < g.V; i++) {for (const std::size_t to : g.edge[i]) { os << i << "->" << to << "\n"; }}return (os << "]\n");}static std::size_t to(const std::size_t e) { return e; }const std::size_t V;std::vector<std::vector<std::size_t>> edge, rev_edge;};using Graph = BaseGraph<void>;using Tree = Graph;template <typename Cost>using CostGraph = BaseGraph<Cost>;template <typename Cost>using CostTree = CostGraph<Cost>;//!==============================================================!////! 888888ba oo oo dP dP !////! 88 '8b 88 88 !////! 88 88 dP dP 88 .dP .d8888b. d8888P 88d888b. .d8888b. !////! 88 88 88 88 88888" Y8ooooo. 88 88' '88 88' '88 !////! 88 .8P 88 88 88 '8b. 88 88 88 88. .88 !////! 8888888P dP 88 dP 'YP '88888P' dP dP '88888P8 !////! 88 !////! dP !////!==============================================================!//template <typename Cost>std::vector<Cost> Dijkstra(const CostGraph<Cost>& g, const std::size_t s){std::vector<Cost> d(g.V, std::numeric_limits<Cost>::max());using P = std::pair<Cost, std::size_t>;std::priority_queue<P, std::vector<P>, std::greater<P>> q;d[s] = 0, q.push({0, s});while (not q.empty()) {const Cost cost = q.top().first;const std::size_t v = q.top().second;q.pop();if (d[v] < cost) { continue; }for (const auto& e : g.edge[v]) {if (d[e.to] <= d[v] + e.cost) { continue; }d[e.to] = d[v] + e.cost, q.push({d[e.to], e.to});}}return d;}//!=====================================!////! 8888ba.88ba oo !////! 88 '8b '8b !////! 88 88 88 .d8888b. dP 88d888b. !////! 88 88 88 88' '88 88 88' '88 !////! 88 88 88 88. .88 88 88 88 !////! dP dP dP '88888P8 dP dP dP !////!=====================================!//int main(){const ll X = read<ll>(), Y = read<ll>(), Z = read<ll>();CostGraph<ll> G(4);G.addEdge(0, 1, 2LL * std::min({X, Y, Z}), true);char S[2];int T[2];for (int i = 0; i < 2; i++) {std::cin >> S[i] >> T[i];G.addEdge(0, 2 + i, 2LL * T[i] - 1, true);if (S[i] == 'A') {G.addEdge(1, 2 + i, 2LL * X - (2LL * T[i] - 1), true);} else if (S[i] == 'B') {G.addEdge(1, 2 + i, 2LL * Y - (2LL * T[i] - 1), true);} else {G.addEdge(1, 2 + i, 2LL * Z - (2LL * T[i] - 1), true);}}if (S[0] == S[1]) { G.addEdge(2, 3, std::abs(T[0] - T[1]) * 2LL, true); }std::cout << Dijkstra(G, 2)[3] / 2 << std::endl;return 0;}