結果
問題 | No.20 砂漠のオアシス |
ユーザー | kurenai3110 |
提出日時 | 2016-12-13 14:45:50 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 3,257 ms / 5,000 ms |
コード長 | 1,551 bytes |
コンパイル時間 | 690 ms |
コンパイル使用メモリ | 64,188 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-13 05:44:26 |
合計ジャッジ時間 | 16,094 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 21 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <string>using namespace std;#define INF (int)1e7vector<int>L;int N, V, Ox, Oy,O;int status[40000];int cost[40000];//int trace[40000];void dijkstra(int s) {int dir[] = { -1 * N,1,1 * N,-1 };int minv;for (int i = 0; i < N*N; i++) {status[i] = 0;cost[i] = INF;}cost[s] = 0;//trace[s] = -1;status[s] = 1;while (1) {minv = INF;int u = -1;//探索が終わってない中でコスト最小の点を探るfor (int i = 0; i < N*N; i++) {if (minv > cost[i] && status[i] != -1) {u = i;minv = cost[i];}}if (u == -1)break;status[u] = -1;//コスト最少の点を探るfor (int i = 0; i < 4; i++) {if (status[u + dir[i]] != -1 && u + dir[i] >= 0 && u + dir[i] < N*N) {if ((dir[i] == 1 || dir[i] == -1) && (u + dir[i]) / N != u / N)continue;if (cost[u + dir[i]] > cost[u] + L[u + dir[i]]) {cost[u + dir[i]] = cost[u] + L[u + dir[i]];status[u + dir[i]] = 1;}}}}}int main(){cin >> N >> V >> Ox >> Oy;Ox--; Oy--; O = Oy * N + Ox;bool hasOasis = O >= 0;L.resize(N*N);for (int i = 0; i < N*N; i++) {cin >> L[i];}dijkstra(0);//cout << cost[N*N - 1] << endl;if (cost[N*N - 1] < V) {cout << "YES" << endl;return 0;}else if(hasOasis){V = (V - cost[O]) * 2;//cout << V << endl;dijkstra(O);//cout << cost[N*N - 1] << endl;if (cost[N*N - 1] < V) {cout << "YES" << endl;return 0;}}cout << "NO" << endl;return 0;}