結果
問題 | No.20 砂漠のオアシス |
ユーザー | Twizz |
提出日時 | 2017-05-23 11:18:11 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 43 ms / 5,000 ms |
コード長 | 1,498 bytes |
コンパイル時間 | 1,385 ms |
コンパイル使用メモリ | 152,952 KB |
実行使用メモリ | 5,000 KB |
最終ジャッジ日時 | 2023-08-03 08:20:59 |
合計ジャッジ時間 | 2,737 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
4,456 KB |
testcase_01 | AC | 2 ms
4,544 KB |
testcase_02 | AC | 3 ms
4,752 KB |
testcase_03 | AC | 5 ms
4,644 KB |
testcase_04 | AC | 3 ms
4,660 KB |
testcase_05 | AC | 41 ms
5,000 KB |
testcase_06 | AC | 43 ms
4,740 KB |
testcase_07 | AC | 43 ms
4,712 KB |
testcase_08 | AC | 32 ms
4,676 KB |
testcase_09 | AC | 43 ms
4,824 KB |
testcase_10 | AC | 3 ms
4,488 KB |
testcase_11 | AC | 3 ms
4,628 KB |
testcase_12 | AC | 4 ms
4,504 KB |
testcase_13 | AC | 4 ms
4,508 KB |
testcase_14 | AC | 6 ms
4,544 KB |
testcase_15 | AC | 5 ms
4,648 KB |
testcase_16 | AC | 11 ms
4,552 KB |
testcase_17 | AC | 8 ms
4,612 KB |
testcase_18 | AC | 9 ms
4,756 KB |
testcase_19 | AC | 10 ms
4,552 KB |
testcase_20 | AC | 4 ms
4,628 KB |
コンパイルメッセージ
main.cpp: In function ‘int dijkstra(PI, PI, int)’: main.cpp:25:78: warning: overflow in conversion from ‘ll’ {aka ‘long long int’} to ‘int’ changes value from ‘10000000000’ to ‘1410065408’ [-Woverflow] rep(i, 0, n + 2)dist[0][i] = dist[i][0] = dist[n + 1][i] = dist[i][n + 1] = mod; ^~~
ソースコード
#include"bits/stdc++.h" //#include<bits/stdc++.h> using namespace std; #define print(x) cout<<x<<endl; #define rep(i,a,b) for(int i=a;i<b;i++) #define REP(i,a) for(int i=0;i<a;i++) typedef long long ll; typedef pair<int, int> PI; typedef pair<int, PI> V; const ll mod = 10000000000; int n, v, ox, oy; int l[202][202] = {}; bool used[202][202] = {}; int dx[4] = { 1,0,-1,0 }; int dy[4] = { 0,1,0,-1 }; struct edge { int to, cost; }; vector<edge> G[202][202]; int dijkstra(PI s,PI t,int n) { int dist[202][202] = {}; rep(i,1,n+1)rep(j,1,n+1) {dist[i][j] = -1;} rep(i, 0, n + 2)dist[0][i] = dist[i][0] = dist[n + 1][i] = dist[i][n + 1] = mod; priority_queue<V, vector<V>, greater<V>>que; que.push(make_pair(0, s)); while (!que.empty()) { PI v = que.top().second; int di = que.top().first; que.pop(); if (dist[v.first][v.second] >= 0)continue; dist[v.first][v.second] = di; rep(i, 0, 4) { PI p = v; p.first += dx[i]; p.second += dy[i]; if (dist[p.first][p.second] >= 0)continue; que.push(make_pair(di + l[p.first][p.second], p)); } } return dist[t.first][t.second]; } int main() { PI o; cin >> n >> v >> o.second >> o.first; rep(i,1,n+1)rep(j,1, n+1) { cin >> l[i][j]; } auto st = make_pair(1, 1); auto ed = make_pair(n, n); if (dijkstra(st, ed, n) < v) { print("YES") } else { int u = (v - dijkstra(st, o, n)) * 2; if ((o.first != 0 || o.second != 0) && u > 0 && u - dijkstra(o, ed, n) > 0) { print("YES"); } else { print("NO"); } } return 0; }