結果

問題 No.867 避難経路
コンテスト
ユーザー MICHAEL
提出日時 2026-07-21 21:58:56
言語 C++23(gcc16)
(gcc 16.1.0 + boost 1.90.0)
コンパイル:
g++-16 -O2 -lm -std=c++23 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 2,460 ms / 6,000 ms
+ 96µs
コード長 2,901 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 4,259 ms
コンパイル使用メモリ 367,192 KB
実行使用メモリ 19,968 KB
最終ジャッジ日時 2026-07-21 22:00:14
合計ジャッジ時間 75,023 ms
ジャッジサーバーID
（参考情報） 		judge3_1 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 41
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct P{
    int x,y;
    ll k,ans;
};
int main(){
    int h,w;
    cin>>h>>w;
    int gx,gy;
    cin>>gx>>gy;
    gx--;
    gy--;
    vector<vector<ll>> a(h,vector<ll>(w));
    for(int i=0;i<h;i++){
        for(int j=0;j<w;j++){
            cin>>a[i][j];
        }
    }
    int q;
    cin>>q;
    vector<P> query(q);
    for(auto &e:query){
        cin>>e.x>>e.y>>e.k;
        e.x--;
        e.y--;
    }
    const int K=300;
    vector<vector<int>> small(K);
    for(int i=0;i<q;i++){
        if(query[i].k<K){
            small[query[i].k].push_back(i);
        }
    }
    int dx[4]={-1,1,0,0};
    int dy[4]={0,0,-1,1};
    vector<vector<ll>> dist(h,vector<ll>(w));
    for(int k=1;k<K;k++){
        for(int i=0;i<h;i++){
            fill(dist[i].begin(),dist[i].end(),LLONG_MAX);
        }
        priority_queue<pair<ll,pair<int,int>>,vector<pair<ll,pair<int,int>>>,greater<pair<ll,pair<int,int>>>> pq;
        dist[gx][gy]=0;
        pq.push({0,{gx,gy}});
        ll add=1LL*k*k;
        while(!pq.empty()){
            auto [d,pos]=pq.top();
            pq.pop();
            int x=pos.first;
            int y=pos.second;
            if(d!=dist[x][y]){
                continue;
            }
            ll nd=d+a[x][y]+add;
            for(int i=0;i<4;i++){
                int nx=x+dx[i];
                int ny=y+dy[i];
                if(nx>=0&&nx<h&&ny>=0&&ny<w){
                    if(dist[nx][ny]>nd){
                        dist[nx][ny]=nd;
                        pq.push({nd,{nx,ny}});
                    }
                }
            }
        }
        for(int id:small[k]){
            int x=query[id].x;
            int y=query[id].y;
            query[id].ans=dist[x][y]+a[x][y]+add;
        }
    }
    vector<vector<pair<int,ll>>> d(h,vector<pair<int,ll>>(w,{INT_MAX,LLONG_MAX}));
    priority_queue<pair<pair<int,ll>,pair<int,int>>,vector<pair<pair<int,ll>,pair<int,int>>>,greater<pair<pair<int,ll>,pair<int,int>>>> pq;
    d[gx][gy]={0,0};
    pq.push({{0,0},{gx,gy}});
    while(!pq.empty()){
        auto cur=pq.top();
        pq.pop();
        int x=cur.second.first;
        int y=cur.second.second;
        auto now=cur.first;
        if(d[x][y]<now){
            continue;
        }
        pair<int,ll> nxt={now.first+1,now.second+a[x][y]};
        for(int i=0;i<4;i++){
            int nx=x+dx[i];
            int ny=y+dy[i];
            if(nx>=0&&nx<h&&ny>=0&&ny<w){
                if(d[nx][ny]>nxt){
                    d[nx][ny]=nxt;
                    pq.push({nxt,{nx,ny}});
                }
            }
        }
    }
    for(auto &e:query){
        if(e.k>=K){
            int len=d[e.x][e.y].first+1;
            ll val=d[e.x][e.y].second+a[e.x][e.y];
            e.ans=val+e.k*e.k*len;
        }
    }
    for(auto e:query){
        cout<<e.ans<<endl;
    }
    return 0;
}
0