結果
問題 | No.34 砂漠の行商人 |
ユーザー | vwxyz |
提出日時 | 2023-12-19 07:32:42 |
言語 | C++17(clang) (17.0.6 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 1,797 ms / 5,000 ms |
コード長 | 1,666 bytes |
コンパイル時間 | 2,796 ms |
コンパイル使用メモリ | 166,596 KB |
実行使用メモリ | 146,688 KB |
最終ジャッジ日時 | 2023-12-19 07:33:10 |
合計ジャッジ時間 | 22,325 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge14 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 4 ms
6,676 KB |
testcase_01 | AC | 2 ms
6,676 KB |
testcase_02 | AC | 12 ms
6,676 KB |
testcase_03 | AC | 9 ms
6,676 KB |
testcase_04 | AC | 179 ms
21,760 KB |
testcase_05 | AC | 277 ms
31,616 KB |
testcase_06 | AC | 106 ms
15,616 KB |
testcase_07 | AC | 564 ms
54,656 KB |
testcase_08 | AC | 961 ms
85,248 KB |
testcase_09 | AC | 688 ms
66,816 KB |
testcase_10 | AC | 1,322 ms
144,512 KB |
testcase_11 | AC | 822 ms
146,176 KB |
testcase_12 | AC | 197 ms
22,912 KB |
testcase_13 | AC | 1,784 ms
146,688 KB |
testcase_14 | AC | 1,797 ms
138,496 KB |
testcase_15 | AC | 228 ms
26,496 KB |
testcase_16 | AC | 208 ms
24,064 KB |
testcase_17 | AC | 730 ms
64,384 KB |
testcase_18 | AC | 17 ms
6,676 KB |
testcase_19 | AC | 1,499 ms
126,464 KB |
testcase_20 | AC | 1,625 ms
134,336 KB |
testcase_21 | AC | 1,698 ms
142,592 KB |
testcase_22 | AC | 1,354 ms
115,328 KB |
testcase_23 | AC | 373 ms
39,680 KB |
testcase_24 | AC | 1,543 ms
126,592 KB |
testcase_25 | AC | 598 ms
59,412 KB |
ソースコード
#include <iostream> #include <queue> #include <vector> #include <climits> #include <bits/stdc++.h> using namespace std; int main() { int N, V, Sy, Sx, Gy, Gx; cin >> N >> V >> Sy >> Sx >> Gy >> Gx; Sx--; Sy--; Gx--; Gy--; vector<vector<int>> L(N, vector<int>(N)); for (int i = 0; i < N; ++i) { for (int j = 0; j < N; ++j) { cin >> L[i][j]; } } const long long inf = LLONG_MAX; vector<vector<long long>> dist(18 * N, vector<long long>(N * N, inf)); dist[0][Sx * N + Sy] = 0; deque<tuple<long long, int, int, int>> queue; queue.push_back(make_tuple(0, 0, Sx, Sy)); while (!queue.empty()) { tuple<long long, int, int, int> tup = queue.front(); long long d = get<0>(tup); int v = get<1>(tup); int x = get<2>(tup); int y = get<3>(tup); queue.pop_front(); if (dist[v][x * N + y] < d) { continue; } for (auto [dx, dy] : vector<pair<int, int>>{{0, 1}, {1, 0}, {0, -1}, {-1, 0}}) { int xx = x + dx; int yy = y + dy; if (0 <= xx && xx < N && 0 <= yy && yy < N) { int vv = v + L[xx][yy]; if (vv < 18 * N && dist[vv][xx * N + yy] > d + 1) { dist[vv][xx * N + yy] = d + 1; queue.push_back({d + 1, vv, xx, yy}); } } } } long long ans = inf; for (int v = 0; v < 18 * N; ++v) { if (v < V) { ans = min(ans, dist[v][Gx * N + Gy]); } } if (ans == inf) { ans = -1; } cout << ans << endl; return 0; }