結果
問題 | No.20 砂漠のオアシス |
ユーザー |
|
提出日時 | 2022-03-21 14:22:06 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 5,000 ms |
コード長 | 1,450 bytes |
コンパイル時間 | 5,061 ms |
コンパイル使用メモリ | 258,672 KB |
最終ジャッジ日時 | 2025-01-28 10:54:03 |
ジャッジサーバーID (参考情報) |
judge2 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include<bits/stdc++.h> using namespace std; #include<atcoder/all> using namespace atcoder; using ll = long long; int n,v,ox,oy; vector<vector<int>> L; int dx[] = {1,0,-1,0},dy[] = {0,1,0,-1}; using P = pair<int,int>; void solve(){ vector<vector<P>> G(n*n); for(int i = 0;i<n;i++){ for(int j = 0;j<n;j++){ int st = i*n+j; for(int k = 0;k<4;k++){ if(i+dx[k]<0||i+dx[k]>=n||j+dy[k]<0||j+dy[k]>=n)continue; int ed = (i+dx[k])*n + (j+dy[k]); G[st].push_back(P(ed,L[i+dx[k]][j+dy[k]])); } } } auto dijkstra = [&](int st,int ed){ priority_queue<P,vector<P>,greater<>>PQ; vector<int> dist(n*n,INT_MAX); PQ.push(P(0,st)); dist[st] = 0; while(PQ.size()){ auto [curCost,cur] = PQ.top(); PQ.pop(); if(curCost!=dist[cur])continue; for(auto &[to,toCost]:G[cur]){ if(dist[to]>curCost+toCost){ dist[to] = curCost+toCost; PQ.push(P(dist[to],to)); } } } return dist[ed]; }; bool is = false; if(dijkstra(0,n*n-1)<v){ is = true; } if(ox==-1&&oy==-1){ if(is)cout<<"YES"<<endl; else cout<<"NO"<<endl; return; } if((v-dijkstra(0,ox*n+oy))*2>dijkstra(ox*n+oy,n*n-1)){ is = true; } if(is)cout<<"YES"<<endl; else cout<<"NO"<<endl; } signed main(){ cin.tie(nullptr); ios::sync_with_stdio(false); cin >> n >> v >> ox >> oy; L = vector<vector<int>>(n,vector<int>(n)); for(int i = 0;i<n;i++){ for(int j = 0;j<n;j++)cin >> L[i][j]; } ox--; oy--; swap(ox,oy); solve(); }