結果
問題 | No.34 砂漠の行商人 |
ユーザー | srup٩(๑`н´๑)۶ |
提出日時 | 2016-09-13 15:24:24 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 792 ms / 5,000 ms |
コード長 | 1,156 bytes |
コンパイル時間 | 776 ms |
コンパイル使用メモリ | 74,312 KB |
実行使用メモリ | 478,080 KB |
最終ジャッジ日時 | 2023-09-10 19:25:58 |
合計ジャッジ時間 | 8,613 ms |
ジャッジサーバーID (参考情報) |
judge13 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 166 ms
476,636 KB |
testcase_01 | AC | 163 ms
476,504 KB |
testcase_02 | AC | 164 ms
476,840 KB |
testcase_03 | AC | 165 ms
476,648 KB |
testcase_04 | AC | 171 ms
476,740 KB |
testcase_05 | AC | 171 ms
476,732 KB |
testcase_06 | AC | 164 ms
476,720 KB |
testcase_07 | AC | 173 ms
476,704 KB |
testcase_08 | AC | 177 ms
476,988 KB |
testcase_09 | AC | 329 ms
477,452 KB |
testcase_10 | AC | 175 ms
476,876 KB |
testcase_11 | AC | 524 ms
477,960 KB |
testcase_12 | AC | 166 ms
476,776 KB |
testcase_13 | AC | 792 ms
478,080 KB |
testcase_14 | AC | 637 ms
477,972 KB |
testcase_15 | AC | 166 ms
476,712 KB |
testcase_16 | AC | 189 ms
477,016 KB |
testcase_17 | AC | 166 ms
476,880 KB |
testcase_18 | AC | 166 ms
476,828 KB |
testcase_19 | AC | 300 ms
477,676 KB |
testcase_20 | AC | 390 ms
477,952 KB |
testcase_21 | AC | 165 ms
476,884 KB |
testcase_22 | AC | 168 ms
476,824 KB |
testcase_23 | AC | 164 ms
476,836 KB |
testcase_24 | AC | 474 ms
477,928 KB |
testcase_25 | AC | 180 ms
476,856 KB |
ソースコード
#include <iostream> #include <algorithm> #include <queue> #include <tuple> #include <cstdio> using namespace std; typedef long long ll; #define rep(i,n) for(int i=0;i<(n);i++) const int INF = 1e8; int dy[] = {1, 0, -1, 0}; int dx[] = {0, 1, 0, -1}; int n, v, sx, sy, gx, gy; int cost[110][110];//cost[i][j] i->jのコスト //used[y][x][t] := (x,y)に残り体力tで行くときの最短時間 int used[110][110][10010]; int main(void){ cin >> n >> v >> sx >> sy >> gx >> gy; sx--; sy--; gx--; gy--; rep(i, n)rep(j, n) cin >> cost[i][j]; rep(i, 110)rep(j, 110)rep(k, 10010)used[i][j][k] = INF; queue<tuple<int, int, int>> q; q.push(make_tuple(sy, sx, v)); used[sy][sx][v] = 0; while(!q.empty()){ int y, x, t; tie(y, x, t) = q.front(); q.pop(); if(y == gy && x == gx){ printf("%d\n", used[y][x][t]); return 0; } rep(i, 4){ int ny = y + dy[i], nx = x + dx[i]; if(!(0 <= ny && ny < n && 0 <= nx && nx < n)) continue; int nv = t - cost[ny][nx]; if(nv <= 0) continue; if(used[ny][nx][nv] != INF) continue; used[ny][nx][nv] = used[y][x][t] + 1; q.push(make_tuple(ny, nx, nv)); } } printf("-1\n"); return 0; }