結果
問題 | No.20 砂漠のオアシス |
ユーザー | ninoinui |
提出日時 | 2020-07-22 14:19:42 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 38 ms / 5,000 ms |
コード長 | 1,989 bytes |
コンパイル時間 | 2,410 ms |
コンパイル使用メモリ | 211,148 KB |
最終ジャッジ日時 | 2025-01-12 01:56:55 |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; template<typename T> class Dijkstra { public: struct edge { int to; T cost; }; int V; vector<vector<edge>> G; vector<T> dist; using pti = pair<T,int>; Dijkstra(int n) : V(n), G(V), dist(V, numeric_limits<T>::max()) {} void add(int u, int v, T cost) { G.at(u).push_back((edge) {v, cost}); } void solve(int s) { priority_queue<pti, vector<pti>, greater<pti>> Q; dist.at(s) = 0; Q.push(pti(0, s)); while (!Q.empty()) { pti p = Q.top(); Q.pop(); int v = p.second; if (dist.at(v) < p.first) continue; for (auto &w : G.at(v)) { if (dist.at(w.to) > dist.at(v) + w.cost) { dist.at(w.to) = dist.at(v) + w.cost; Q.push(pti(dist.at(w.to), w.to)); } } } } }; int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int N, V, ow, oh; cin >> N >> V >> ow >> oh; ow--, oh--; int O = oh * N + ow; vector<vector<pair<int, int>>> L(N, vector<pair<int, int>>(N)); for (int i = 0, id = 0; i < N; i++) { for (int j = 0; j < N; j++) { int l; cin >> l; L.at(i).at(j) = {id++, l}; } } vector<int> mh(4), mw(4); mh = {-1, 0, 1, 0}; mw = {0, 1, 0, -1}; Dijkstra<int> D(N * N); for (int h = 0; h < N; h++) { for (int w = 0; w < N; w++) { for (int i = 0; i < 4; i++) { int nh = h + mh.at(i); int nw = w + mw.at(i); if (nh < 0 || nh >= N || nw < 0 || nw >= N) continue; auto [a, b] = L.at(h).at(w); auto [c, d] = L.at(nh).at(nw); D.add(a, c, d); } } } Dijkstra<int> D1 = D; D1.solve(0); if (D1.dist.at(N * N - 1) < V) return cout << "YES" << "\n", 0; if (ow == -1) return cout << "NO" << "\n", 0; if (D1.dist.at(O) >= V) return cout << "NO" << "\n", 0; V -= D1.dist.at(O); V *= 2; Dijkstra<int> DO = D; DO.solve(O); if (DO.dist.at(N * N - 1) < V) cout << "YES" << "\n"; else cout << "NO" << "\n"; }