結果

問題 No.20 砂漠のオアシス
ユーザー furonfuron
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0