結果
問題 | No.20 砂漠のオアシス |
ユーザー | furon |
提出日時 | 2023-05-31 13:34:17 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 21 ms / 5,000 ms |
コード長 | 2,144 bytes |
コンパイル時間 | 1,637 ms |
コンパイル使用メモリ | 138,696 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-28 13:46:52 |
合計ジャッジ時間 | 2,552 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream>#include <iomanip>#include <vector>#include <algorithm>#include <functional>#include <cmath>#include <string>#include <queue>#include <map>#include <bitset>#include <set>#include <stack>#include <numeric>#include <unordered_map>#include <random>using namespace std;using ll = long long;using vi = vector<int>;using vvi = vector<vi>;using vl = vector<ll>;using vvl = vector<vl>;using vb = vector<bool>;using vvb = vector<vb>;using vd = vector<double>;using vs = vector<string>;using pii = pair<int, int>;using pll = pair<ll, ll>;using pdd = pair<double, double>;using vpii = vector<pii>;using vpll = vector<pll>;using vpdd = vector<pdd>;const int inf = (1 << 30) - 1;const ll INF = 1LL << 60;const int MOD = 1000000007;//const int MOD = 998244353;struct Point {int x, y;ll c;bool operator>(const Point& right) const {return c == right.c ? x > right.x : c > right.c;}};const int dy[4] = { -1,0,1,0 };const int dx[4] = { 0,1,0,-1 };void dijkstra2d(const vvi& g, int h, int w, int sy, int sx, vvl& cost) {cost.assign(h, vl(w, INF));priority_queue<Point, vector<Point>, greater<Point>> pq;cost[sy][sx] = 0;pq.push({ sx, sy, 0 });while (!pq.empty()) {Point p = pq.top();pq.pop();for (int i = 0; i < 4; i++) {int y2 = p.y + dy[i];int x2 = p.x + dx[i];if (y2 < 0 || y2 > h - 1 || x2 < 0 || x2 > w - 1) continue;ll c = p.c + g[y2][x2];if (cost[y2][x2] > c) {cost[y2][x2] = c;pq.push({ x2, y2, c });}}}}int main() {int n, v, ox, oy;cin >> n >> v >> ox >> oy;ox--; oy--;vvi g(n, vi(n));int h = n, w = n;for (int y = 0; y < h; y++) {for (int x = 0; x < w; x++) {cin >> g[y][x];}}vvl cost;dijkstra2d(g, h, w, 0, 0, cost);if (cost[h - 1][w - 1] < v) {cout << "YES" << endl;return 0;}if (oy == -1) {cout << "NO" << endl;return 0;}if (cost[oy][ox] >= v) {cout << "NO" << endl;return 0;}v = (v - cost[oy][ox]) * 2;vvl cost2;dijkstra2d(g, h, w, oy, ox, cost2);if (cost2[h - 1][w - 1] < v) cout << "YES" << endl;else cout << "NO" << endl;return 0;}