結果
問題 | No.20 砂漠のオアシス |
ユーザー | E31415926 |
提出日時 | 2016-11-28 19:17:39 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 20 ms / 5,000 ms |
コード長 | 2,447 bytes |
コンパイル時間 | 1,732 ms |
コンパイル使用メモリ | 174,480 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-13 05:40:34 |
合計ジャッジ時間 | 2,509 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>using namespace std;#define FOR(i,a,b) for (int i=(a);i<(b);i++)#define RFOR(i,a,b) for (int i=(b)-1;i>=(a);i--)#define REP(i,n) for (int i=0;i<(n);i++)#define rep(i,n) for (int i=0;i<(n);i++)#define RREP(i,n) for (int i=(n)-1;i>=0;i--)#define ALL(a) (a).begin(),(a).end()#define all(a) (a).begin(),(a).end()#define EXIST(s,e) (find(all(s),(e))!=(s).end())#define exist(s,e) (find(all(s),(e))!=(s).end())#define FINDi(s,e) distance((s).begin(),find(all(s),(e)))#define INF (1<<25)#define ll long long#define VS vector<string>#define VI vector<int>#define vi vector<int>#define VI2 vector<vector<int>>#define vi2 vector<vector<int>>#define v2Resize(s,x,y) s.resize(x); REP(i,s.size()) s[i].resize(y);#define v2Fill(s,v) REP(v2filliiiiiii,s.size()) fill(all(s[v2filliiiiiii]),v);#define Pii pair<int,int>#define P pair;#define in1(x,m) REP(in1iiiiiiiiiiii,m){int tmpForIn1Macrofjaio; cin>>tmpForIn1Macrofjaio; x.push_back(tmpForIn1Macrofjaio);}#define in2(v2,x,y) REP(in2iiiiiiiiiiiiii,x) REP(in2jjjjjjjjj,y) cin>>v2[in2iiiiiiiiiiiiii][in2jjjjjjjjj];#define OUT2(v2) REP(out2iiiiiiiii,v2.size()){ REP(out2jjjjjjjjjjj,v2[out2iiiiiiiii].size()){ cout<<v2[out2iiiiiiiii][out2jjjjjjjjjjj] << " ";}cout<<endl;};const int mod = 1000000007;int dy4[] = {0, 0, 1, -1};int dx4[] = {1, -1, 0, 0};int dx8[] = {0,1,1,1,0,-1,-1,-1};int dy8[] = {-1,-1,0,1,1,1,0,-1};int n;int V;int ox, oy;int L[210][210];int dist[210][210];typedef pair<int, Pii> PP;void dijkstra(int y, int x) {priority_queue<PP, vector<PP>, greater<PP>> que;rep(i, n)rep(j, n)dist[i][j] = INF;dist[y][x] = 0;que.push(make_pair(0,Pii(y, x)));while (!que.empty()) {int c = que.top().first;auto now = que.top().second;que.pop();rep(i,4) {int ny = now.first + dy4[i], nx = now.second + dx4[i];if (!(0 <= ny && ny < n && 0 <= nx && nx < n))continue;if (dist[ny][nx] <= c + L[ny][nx])continue;dist[ny][nx] = c + L[ny][nx];que.push(make_pair(dist[ny][nx], Pii(ny, nx)));}}}int main() {cin >> n >> V >> ox >> oy;ox--;oy--;rep(y, n)rep(x, n)cin >> L[y][x];dijkstra(0, 0);if (dist[n - 1][n - 1] < V) {cout << "YES" << endl;return 0;}if (ox == -1 && oy == -1) {cout << "NO" << endl;return 0;}int t = (V - dist[oy][ox]) * 2;dijkstra(oy, ox);if (t - dist[n - 1][n - 1] > 0) {cout << "YES" << endl;}else {cout << "NO" << endl;}return 0;}