結果
問題 | No.20 砂漠のオアシス |
ユーザー |
![]() |
提出日時 | 2016-12-13 14:51:39 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 3,434 ms / 5,000 ms |
コード長 | 1,622 bytes |
コンパイル時間 | 537 ms |
コンパイル使用メモリ | 63,488 KB |
実行使用メモリ | 6,820 KB |
最終ジャッジ日時 | 2024-10-13 05:44:41 |
合計ジャッジ時間 | 13,400 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
6,820 KB |
testcase_01 | AC | 1 ms
6,820 KB |
testcase_02 | AC | 2 ms
6,820 KB |
testcase_03 | AC | 8 ms
6,820 KB |
testcase_04 | AC | 9 ms
6,816 KB |
testcase_05 | AC | 3,434 ms
6,820 KB |
testcase_06 | AC | 425 ms
6,820 KB |
testcase_07 | AC | 3,116 ms
6,820 KB |
testcase_08 | AC | 1,638 ms
6,820 KB |
testcase_09 | AC | 2,813 ms
6,816 KB |
testcase_10 | AC | 2 ms
6,820 KB |
testcase_11 | AC | 1 ms
6,820 KB |
testcase_12 | AC | 9 ms
6,816 KB |
testcase_13 | AC | 13 ms
6,816 KB |
testcase_14 | AC | 44 ms
6,816 KB |
testcase_15 | AC | 25 ms
6,820 KB |
testcase_16 | AC | 201 ms
6,820 KB |
testcase_17 | AC | 89 ms
6,816 KB |
testcase_18 | AC | 152 ms
6,820 KB |
testcase_19 | AC | 205 ms
6,816 KB |
testcase_20 | AC | 5 ms
6,820 KB |
ソースコード
#include <iostream> #include <vector> #include <algorithm> #include <string> using namespace std; #define INF (int)1e7 vector<int>L; int N, V, Ox, Oy,O; int status[40000]; int cost[40000]; //int trace[40000]; void dijkstra(int s,int t) { 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 || u==t)break; if (cost[u] >= V)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,N*N-1); //cout << cost[N*N - 1] << endl; if (cost[N*N - 1] < V) { cout << "YES" << endl; return 0; } else if(hasOasis){ dijkstra(0, O); V = (V - cost[O]) * 2; //cout << V << endl; dijkstra(O,N*N-1); //cout << cost[N*N - 1] << endl; if (cost[N*N - 1] < V) { cout << "YES" << endl; return 0; } } cout << "NO" << endl; return 0; }