結果
問題 | No.20 砂漠のオアシス |
ユーザー | Darjeeling0 |
提出日時 | 2020-03-04 00:42:53 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 69 ms / 5,000 ms |
コード長 | 3,184 bytes |
コンパイル時間 | 2,185 ms |
コンパイル使用メモリ | 187,192 KB |
実行使用メモリ | 5,912 KB |
最終ジャッジ日時 | 2024-10-13 23:24:39 |
合計ジャッジ時間 | 3,119 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <bits/stdc++.h>#define REP(i, n) for (int i = 0; i < (int)(n); i++)#define REPR(i, n) for(int i = (int)(n); i >= 0; i--)#define FOR(i, s, n) for (int i = (s); i < (int)(n); i++)#define ALL(v) v.begin(), v.iner()using namespace std;typedef long long ll;ll N, K, W, H, M, C, V;const int MAX = 510000;const int MOD = 1000000007;long long fac[MAX], finv[MAX], inv[MAX];vector<double> cx, cy, c;ll MM = 1e12;void COMinit() {fac[0] = fac[1] = 1;finv[0] = finv[1] = 1;inv[1] = 1;for (int i = 2; i < MAX; i++){fac[i] = fac[i - 1] * i % MOD;inv[i] = MOD - inv[MOD%i] * (MOD / i) % MOD;finv[i] = finv[i - 1] * inv[i] % MOD;}}long long COM(int n, int k){if (n < k) return 0;if (n < 0 || k < 0) return 0;return fac[n] * (finv[k] * finv[n - k] % MOD) % MOD;}std::vector<int> Eratosthenes(int n ){std::vector<bool> is_prime( n + 1 );for( int i = 0; i <= n; i++ ) is_prime[ i ] = true;std::vector<int> P;for( int i = 2; i <= n; i++ ){if( is_prime[ i ] ){for( int j = 2 * i; j <= n; j += i ){is_prime[ j ] = false;}P.emplace_back( i );}}return P;}vector<pair<int, int>> edge(pair<int, int> u){vector<pair<int, int>> ret;int i = u.first, j = u.second;if(i > 0) {ret.push_back(make_pair(i-1, j));}if(j > 0) {ret.push_back(make_pair(i, j-1));}if(i < N-1) {ret.push_back(make_pair(i + 1, j));}if(j < N-1) {ret.push_back(make_pair(i , j + 1));}return ret;}ll Dijkstra(pair<int, int> init, pair<int, int> iner, vector<vector<ll>> dist){vector<vector<ll>> cost(N, vector<ll> (N, MM));cost[init.first][init.second] = 0;priority_queue<pair<ll, pair<int, int>>> que;que.push(make_pair( 0, make_pair(init.first, init.second) ));REP(i, N){REP(j ,N){if( i == init.first and j == init.second) continue;que.push(make_pair(-MM, make_pair(i,j)));}}while(!que.empty()){pair<int, int> u = que.top().second;que.pop();for(auto v: edge(u)){ll cnd = cost[u.first][u.second] + dist[v.first][v.second];if(cost[v.first][v.second] > cnd){cost[v.first][v.second] = cnd;que.push(make_pair(-cnd , v));//cout << cnd << " ";}}}// cout << cost[iner.first][iner.second] << " ";return cost[iner.first][iner.second];}int main(){cin >> N >> V;vector<vector<ll>> dist(N, vector<ll> (N, MM));int ox, oy;cin >> oy >> ox;ox--; oy--;REP(i, N){REP(j, N){cin >> dist[i][j];}}if(Dijkstra(make_pair(0,0) , make_pair(N-1, N-1), dist) < V) {cout << "YES"; return 0;}if(ox >= 0 and oy >= 0){ll to_oasis = Dijkstra(make_pair(0,0) , make_pair(ox, oy), dist) ;ll from_oasis = Dijkstra(make_pair(ox, oy), make_pair(N-1, N-1), dist) ;// cout << 2*(V- to_oasis) << " " ;if(from_oasis < 2*(V- to_oasis) ) {cout << "YES";return 0;}}cout << "NO";return 0;}