結果
問題 | No.20 砂漠のオアシス |
ユーザー | ninoinui |
提出日時 | 2020-07-22 14:19:42 |
言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 38 ms / 5,000 ms |
コード長 | 1,989 bytes |
コンパイル時間 | 2,427 ms |
コンパイル使用メモリ | 216,448 KB |
実行使用メモリ | 12,544 KB |
最終ジャッジ日時 | 2023-09-02 12:35:33 |
合計ジャッジ時間 | 3,777 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge13 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,380 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 2 ms
4,376 KB |
testcase_03 | AC | 3 ms
4,380 KB |
testcase_04 | AC | 3 ms
4,380 KB |
testcase_05 | AC | 30 ms
10,692 KB |
testcase_06 | AC | 37 ms
12,544 KB |
testcase_07 | AC | 37 ms
12,264 KB |
testcase_08 | AC | 25 ms
9,456 KB |
testcase_09 | AC | 38 ms
12,268 KB |
testcase_10 | AC | 1 ms
4,376 KB |
testcase_11 | AC | 2 ms
4,380 KB |
testcase_12 | AC | 2 ms
4,380 KB |
testcase_13 | AC | 3 ms
4,376 KB |
testcase_14 | AC | 4 ms
4,376 KB |
testcase_15 | AC | 4 ms
4,376 KB |
testcase_16 | AC | 7 ms
4,904 KB |
testcase_17 | AC | 6 ms
4,468 KB |
testcase_18 | AC | 7 ms
4,776 KB |
testcase_19 | AC | 8 ms
4,956 KB |
testcase_20 | AC | 2 ms
4,376 KB |
ソースコード
#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"; }