結果

問題 No.34 砂漠の行商人
ユーザー tottoripapertottoripaper
提出日時 2014-11-24 02:13:29
言語 C++11
(gcc 11.4.0)
結果
AC  
実行時間 2,678 ms / 5,000 ms
コード長 1,355 bytes
コンパイル時間 536 ms
コンパイル使用メモリ 66,280 KB
実行使用メモリ 403,112 KB
最終ジャッジ日時 2024-06-28 10:06:33
合計ジャッジ時間 18,134 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 261 ms
402,084 KB
testcase_01 AC 260 ms
402,088 KB
testcase_02 AC 262 ms
401,992 KB
testcase_03 AC 262 ms
402,092 KB
testcase_04 AC 278 ms
402,136 KB
testcase_05 AC 284 ms
402,244 KB
testcase_06 AC 265 ms
402,176 KB
testcase_07 AC 292 ms
402,200 KB
testcase_08 AC 306 ms
402,304 KB
testcase_09 AC 952 ms
402,384 KB
testcase_10 AC 307 ms
402,304 KB
testcase_11 AC 1,899 ms
402,860 KB
testcase_12 AC 271 ms
402,168 KB
testcase_13 AC 2,678 ms
403,112 KB
testcase_14 AC 1,999 ms
402,852 KB
testcase_15 AC 262 ms
402,168 KB
testcase_16 AC 354 ms
402,196 KB
testcase_17 AC 261 ms
402,156 KB
testcase_18 AC 267 ms
402,184 KB
testcase_19 AC 781 ms
402,852 KB
testcase_20 AC 1,206 ms
402,988 KB
testcase_21 AC 260 ms
402,156 KB
testcase_22 AC 273 ms
402,344 KB
testcase_23 AC 262 ms
402,176 KB
testcase_24 AC 1,547 ms
402,856 KB
testcase_25 AC 315 ms
402,204 KB
権限があれば一括ダウンロードができます
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:18:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   18 |     scanf("%d %d %d %d %d %d", &N, &V, &SX, &SY, &GX, &GY);
      |     ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
main.cpp:22:18: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
   22 |             scanf("%d", &map[i][j]);
      |             ~~~~~^~~~~~~~~~~~~~~~~~

ソースコード

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