結果

問題 No.34 砂漠の行商人
ユーザー tottoripaper
提出日時 2014-11-24 02:13:29
言語 C++11（廃止可能性あり）
(gcc 13.3.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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます
コンパイルメッセージ
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