#line 1 "grid_Dijkstra.test.cpp" #define PROBLEM "https://yukicoder.me/problems/no/1638" #line 2 "/Users/akagiyasunori/Work/procon/lib/heuristic_lib/data_structures/radix_heap.hpp" #include #include #include #include #include #include #include // Radix heap for unsigned integer // https://github.com/iwiwi/radix-heap // hitonanode さんの radix heap. https://hitonanode.github.io/cplib-cpp/data_structure/radix_heap.hpp template ::value>::type * = nullptr> class radix_heap { int sz; Uint last; std::array>, std::numeric_limits::digits + 1> v; template ::type * = nullptr> static inline int bucket(U x) noexcept { return x ? 32 - __builtin_clz(x) : 0; } template ::type * = nullptr> static inline int bucket(U x) noexcept { return x ? 64 - __builtin_clzll(x) : 0; } void pull() { if (!v[0].empty()) return; int i = 1; while (v[i].empty()) ++i; last = v[i].back().first; for (int j = 0; j < int(v[i].size()); j++) last = std::min(last, v[i][j].first); for (int j = 0; j < int(v[i].size()); j++) { v[bucket(v[i][j].first ^ last)].emplace_back(std::move(v[i][j])); } v[i].clear(); } public: radix_heap() : sz(0), last(0) { static_assert(std::numeric_limits::digits > 0, "Invalid type."); } std::size_t size() const noexcept { return sz; } bool empty() const noexcept { return sz == 0; } void push(Uint x, const Label &val) { ++sz, v[bucket(x ^ last)].emplace_back(x, val); } void push(Uint x, Label &&val) { ++sz, v[bucket(x ^ last)].emplace_back(x, std::move(val)); } template void emplace(Uint x, Args &&...args) { ++sz, v[bucket(x ^ last)].emplace_back(std::piecewise_construct, std::forward_as_tuple(x), std::forward_as_tuple(args...)); } void pop() { pull(), --sz, v[0].pop_back(); } std::pair top() { return pull(), v[0].back(); } Uint top_key() { return pull(), last; } Label &top_label() { return pull(), v[0].back().second; } void clear() noexcept { sz = 0, last = 0; for (auto &vec : v) vec.clear(); } void swap(radix_heap &a) { std::swap(sz, a.sz), std::swap(last, a.last), v.swap(a.v); } }; #line 2 "/Users/akagiyasunori/Work/procon/lib/heuristic_lib/grid/grid_template.hpp" #include using namespace std; using ll = long long; template // T は辺のコストの型 struct grid_template{ const T T_INF = numeric_limits::max(); const int num_dirs = 4; const vector dx = {0, -1, 0, 1}; const vector dy = {-1, 0, 1, 0}; const vector dc = {'L', 'U', 'R', 'D'}; // H: 縦の長さ W: 横の長さ // access: 移動コストを表現する3次元配列.access[x][y][dir] はマス(x, y)から方向dirに進むときのコストを表す.-1の場合は移動不可能. int H, W; vector>> access; vector access_array; bool array_flag = false; grid_template(int H, int W): H(H), W(W){ access.resize(H); for(int i=0;i decode_grid(int x){ return {x / W, x % W}; } void make_access_array(){ for(int i=0;i> bfs(int sx, int sy){ if(!array_flag) make_access_array(); vector dist(H * W, -1); queue qu; int s = encode_grid(sx, sy); dist[s] = 0; qu.emplace(s); while(!qu.empty()){ auto v_cur = qu.front();qu.pop(); auto [cx, cy] = decode_grid(v_cur); for(int i=0;i> dist_grid(H, vector(W)); for(int i=0;i bfs_reconstruction(int sx, int sy, int tx, int ty){ if(!array_flag) make_access_array(); vector dist(H * W, -1); vector pre_v(H * W, -1); queue qu; int s = encode_grid(sx, sy); dist[s] = 0; qu.emplace(s); while(!qu.empty()){ auto v_cur = qu.front();qu.pop(); auto [cx, cy] = decode_grid(v_cur); for(int i=0;i> Dijkstra(int sx, int sy){ if(!array_flag) make_access_array(); int s = encode_grid(sx, sy); vector dist(H * W, T_INF); vector pre_v(H * W, T_INF); using Pi = pair; priority_queue, greater> pq; // radix_heap::type, int> pq; // 符号なし整数にしか使えないが,定数倍が高速 dist[s] = 0; pq.emplace(0, s); while(!pq.empty()){ auto [cost, v_cur] = pq.top();pq.pop(); auto [x_cur, y_cur] = decode_grid(v_cur); if(dist[v_cur] < cost) continue; for(int i=0;i> dist_grid(H, vector(W)); for(int i=0;i Dijkstra_reconstruction(int sx, int sy, int tx, int ty){ if(!array_flag) make_access_array(); int s = encode_grid(sx, sy); vector dist(H * W, T_INF); vector pre_v(H * W, T_INF); using Pi = pair; priority_queue, greater> pq; // radix_heap::type, int> pq; // 符号なし整数にしか使えないが,定数倍が高速 dist[s] = 0; pq.emplace(0, s); while(!pq.empty()){ auto [cost, v_cur] = pq.top();pq.pop(); auto [x_cur, y_cur] = decode_grid(v_cur); if(dist[v_cur] < cost) continue; for(int i=0;i> H >> W; vector C(4); cin >> C[1] >> C[3] >> C[2] >> C[0]; ll K, P; cin >> K >> P; int sx, sy, tx, ty; cin >> sx >> sy >> tx >> ty; sx--, sy--, tx--, ty--; vector S(H); for(int i=0;i> S[i]; } grid_template G(H, W); for(int i=0;i= 0 and nx < H and ny >= 0 and ny < W and S[nx][ny] != '#'){ G.access[i][j][k] = C[k]; if(S[nx][ny] == '@') G.access[i][j][k] += P; } } } } auto dist = G.Dijkstra(sx, sy); // cout << dist[tx][ty] << endl; cout << (dist[tx][ty] <= K ? "Yes" : "No") << endl; }