結果

問題 No.34 砂漠の行商人
コンテスト
ユーザー codershifth
提出日時 2015-07-23 23:25:40
言語 C++11（廃止可能性あり）
(gcc 13.3.0)
結果
AC  
実行時間 40 ms / 5,000 ms
コード長 2,860 bytes
コンパイル時間 1,409 ms
コンパイル使用メモリ 172,136 KB
実行使用メモリ 5,376 KB
最終ジャッジ日時 2024-06-28 10:18:00
合計ジャッジ時間 2,439 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

typedef long long ll;
typedef unsigned long long ull;

#define FOR(i,a,b) for(int (i)=(a);i<(b);i++)
#define REP(i,n) FOR(i,0,n)
#define RANGE(vec) (vec).begin(),(vec).end()

using namespace std;


class DesertChapman {
public:
    void solve(void) {
            int N,V,sx,sy,gx,gy;
            cin>>N>>V>>sx>>sy>>gx>>gy;
            --sx,--sy,--gx,--gy;
            vector<vector<int>> fld(N,vector<int>(N,0));
            REP(i,N)
            REP(j,N)
                cin>>fld[i][j];

            const int inf = (1<<30);

            // cost[y][x] := (x,y) までの到達コストの最小値
            vector<vector<int>> cost(N,vector<int>(N,inf));
            queue<tuple<int,int,int,int>> que;
            // 幅優先探索でやる
            que.emplace(sx,sy,0,0);
            // 最悪ゴールまで辿りつけないケースは全探索になるので
            // O(N^2*V) <= 10^10 となる。
            //
            // ただし障害物がないので
            // ((横の移動最大回数)+(縦の移動最大回数))*max(fld[y][x]) < V なら到達可能なので
            // O(N^2*V) <= 1.8*10^7 程度の計算量になる。
            //
            while (!que.empty())
            {
                int x,y,c,t;
                tie(x,y,c,t) = que.front();
                que.pop();

                const int dx[] = {1,0,-1,0};
                const int dy[] = {0,-1,0,1};
                REP(d,4)
                {
                    int nx = x+dx[d];
                    int ny = y+dy[d];

                    if (nx < 0 || ny < 0 || N <= nx || N <= ny)
                        continue;

                    int nc = c+fld[ny][nx];
                    // 体力が付きてしまった
                    if (nc >= V)
                        continue;

                    // 到達できたら終了。幅優先なのでこれが最短時間
                    if (nx==gx && ny==gy)
                    {
                        cout<<t+1<<endl;
                        return;
                    }
                    // 到達コストを更新できるなら更新して enqueue
                    // 更新前の到達コストの方が到達時間が短い可能性があるが、
                    // その場合はとなりのマスへの移動がすでに enqueu されているはず。
                    if (cost[ny][nx] > nc)
                    {
                        cost[ny][nx] = c+fld[ny][nx];
                        que.emplace(nx,ny,cost[ny][nx],t+1);
                    }
                }
            }
            cout<<-1<<endl;
            return;
    }
};

#if 1
int main(int argc, char *argv[])
{
        ios::sync_with_stdio(false);
        auto obj = new DesertChapman();
        obj->solve();
        delete obj;
        return 0;
}
#endif
0