結果

問題 No.34 砂漠の行商人
ユーザー tottoripapertottoripaper
提出日時 2014-11-24 02:13:29
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2,561 ms / 5,000 ms
コード長 1,355 bytes
コンパイル時間 695 ms
コンパイル使用メモリ 66,540 KB
実行使用メモリ 402,724 KB
最終ジャッジ日時 2023-09-10 18:56:58
合計ジャッジ時間 14,819 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge12
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 130 ms
402,016 KB
testcase_01 AC 131 ms
402,216 KB
testcase_02 AC 131 ms
402,108 KB
testcase_03 AC 129 ms
402,032 KB
testcase_04 AC 153 ms
402,224 KB
testcase_05 AC 154 ms
402,156 KB
testcase_06 AC 131 ms
402,032 KB
testcase_07 AC 169 ms
402,168 KB
testcase_08 AC 186 ms
402,296 KB
testcase_09 AC 844 ms
402,320 KB
testcase_10 AC 182 ms
402,176 KB
testcase_11 AC 1,668 ms
402,720 KB
testcase_12 AC 144 ms
402,156 KB
testcase_13 AC 2,561 ms
402,636 KB
testcase_14 AC 1,867 ms
402,724 KB
testcase_15 AC 134 ms
402,148 KB
testcase_16 AC 231 ms
402,228 KB
testcase_17 AC 130 ms
402,196 KB
testcase_18 AC 138 ms
402,208 KB
testcase_19 AC 654 ms
402,648 KB
testcase_20 AC 1,080 ms
402,656 KB
testcase_21 AC 133 ms
402,060 KB
testcase_22 AC 141 ms
402,304 KB
testcase_23 AC 133 ms
402,100 KB
testcase_24 AC 1,418 ms
402,724 KB
testcase_25 AC 193 ms
402,236 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdio>
#include <queue>
#include <cstring>
#include <vector>

#define mp std::make_pair

typedef std::pair<int,int> P;

const int dx[4] = {-1, 1, 0, 0}, dy[4] = {0, 0, -1, 1};

int N, V, SX, SY, GX, GY;
int map[101][101];
int d[101][101][10001];

int main(){
    scanf("%d %d %d %d %d %d", &N, &V, &SX, &SY, &GX, &GY);

    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            scanf("%d", &map[i][j]);
        }
    }

    std::fill(&d[0][0][0], &d[0][0][0]+101*101*10001, 1001001001);

    std::priority_queue<P, std::vector<P>, std::greater<P>> q;
    q.push(mp(0, SY+101*(SX+101*V)));
    d[SY][SX][V] = 0;

    int res = -1;
    while(!q.empty()){
        P p = q.top(); q.pop();
        int t = p.first,
            x = p.second / 101 % 101,
            y = p.second % 101,
            l = p.second / (101*101);

        if(x == GX && y == GY){res = t; break;}

        for(int i=0;i<4;i++){
            int nx = x + dx[i], ny = y + dy[i];
            if(1 <= nx && nx <= N && 1 <= ny && ny <= N && l - map[ny][nx] > 0 && t+1 < d[ny][nx][l-map[ny][nx]]){
                int nl = l-map[ny][nx];
                d[ny][nx][nl] = t+1;
                q.push(mp(d[ny][nx][nl], ny+101*(nx+101*nl)));
            }
        }
    }

    printf("%d\n", res);
}
0