結果
問題 | No.20 砂漠のオアシス |
ユーザー | granddaifuku |
提出日時 | 2020-03-22 13:05:48 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 19 ms / 5,000 ms |
コード長 | 1,774 bytes |
コンパイル時間 | 2,235 ms |
コンパイル使用メモリ | 177,744 KB |
実行使用メモリ | 5,248 KB |
最終ジャッジ日時 | 2024-12-24 17:21:19 |
合計ジャッジ時間 | 3,253 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h> using namespace std; #define rep(i, n) for(int i = 0; i < (int)n; ++i) #define FOR(i, a, b) for(int i = a; i < (int)b; ++i) #define rrep(i, n) for(int i = ((int)n - 1); i >= 0; --i) typedef long long ll; typedef long double ld; const int Inf = 1e9; const double EPS = 1e-9; const int MOD = 1e9 + 7; int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; int n, v, ox, oy; vector<vector<int> > g; using P = pair<int, int>; using PP = pair<int, P>; vector<vector<int> > dist; void dijkstra(int sx = 0, int sy = 0) { dist = vector<vector<int> >(n, vector<int>(n, Inf)); dist[sx][sy] = 0; priority_queue<PP, vector<PP>, greater<PP> > pq; pq.push(PP(0, P(sx, sy))); while (!pq.empty()) { PP p = pq.top(); pq.pop(); int c = p.first; int vx = p.second.first, vy = p.second.second; rep (i, 4) { int nx, ny; nx = vx + dx[i], ny = vy + dy[i]; if (nx < 0 || ny < 0 || nx >= n || ny >= n) continue; if (dist[nx][ny] <= g[nx][ny] + c) continue; dist[nx][ny] = g[nx][ny] + c; pq.push(PP(dist[nx][ny], P(nx, ny))); } } } int main() { cin.tie(nullptr); ios::sync_with_stdio(0); cin >> n >> v >> oy >> ox; ox--, oy--; g = vector<vector<int> >(n, vector<int>(n)); rep (i, n) rep (j, n) cin >> g[i][j]; dijkstra(); if (dist[n - 1][n - 1] < v) { cout << "YES" << endl; return 0; } if (ox >= 0 && oy >= 0) { int toO = 2 * (v - dist[ox][oy]); dijkstra(ox, oy); int toG = dist[n - 1][n - 1]; if (toG < toO) { cout << "YES" << endl; return 0; } } cout << "NO" << endl; return 0; }