結果
問題 | No.867 避難経路 |
ユーザー |
![]() |
提出日時 | 2024-03-11 15:06:50 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 4,092 ms / 6,000 ms |
コード長 | 3,002 bytes |
コンパイル時間 | 2,140 ms |
コンパイル使用メモリ | 138,924 KB |
最終ジャッジ日時 | 2025-02-20 03:53:29 |
ジャッジサーバーID (参考情報) |
judge5 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <iostream>#include <vector>#include <algorithm>#include <array>#include <iterator>#include <string>#include <cctype>#include <cstring>#include <cstdlib>#include <cassert>#include <cmath>#include <ctime>#include <iomanip>#include <numeric>#include <stack>#include <queue>#include <map>#include <unordered_map>#include <set>#include <unordered_set>#include <bitset>#include <random>#include <utility>#include <functional>using namespace std;void Main(){int H,W,gi,gj;cin >> H >> W >> gi >> gj;gi--; gj--;vector<vector<int>> A(H,vector<int>(W));for(int i = 0;i < H;i++){for(int j = 0;j < W;j++){cin >> A[i][j];}}vector<vector<int>> cost(H,vector<int>(W,(int)1e9));const int d[5] = {0,1,0,-1};cost[gi][gj] = A[gi][gj];auto dfs = [&](auto dfs,int i,int j) -> int{if(cost[i][j] < (int)1e9){return cost[i][j];}int res = (int)1e9;if(i < gi){res = min(res,dfs(dfs,i + 1,j) + A[i][j]);}if(i > gi){res = min(res,dfs(dfs,i - 1,j) + A[i][j]);}if(j < gj){res = min(res,dfs(dfs,i,j + 1) + A[i][j]);}if(j > gj){res = min(res,dfs(dfs,i,j - 1) + A[i][j]);}return cost[i][j] = res;};for(int i = 0;i < H;i++){for(int j = 0;j < W;j++){dfs(dfs,i,j);}}/* { *//* queue<pair<int,int>> Q; *//* Q.push(make_pair(gi,gj)); *//* while(!Q.empty()) *//* { *//* auto [i,j] = Q.front(); *//* Q.pop(); *//* for(int k = 0;k < 4;k++) *//* { *//* int ni = i + d[k]; *//* int nj = j + d[k + 1]; *//* if(ni < 0 || nj < 0 || ni >= H || nj >= W) *//* { *//* continue; *//* } *//* if(cost[ni][nj] == (int)1e9) *//* { *//* Q.push(make_pair(ni,nj)); *//* } *//* cost[ni][nj] = min(cost[ni][nj],cost[i][j] + A[ni][nj]); *//* } *//* } *//* } */const int B = 223;vector<vector<vector<int>>> dp(H,vector<vector<int>>(W,vector<int>(B,(int)1e9)));for(int k = 1;k < B;k++){dp[gi][gj][k] = k * k + A[gi][gj];priority_queue<pair<int,pair<int,int>>> Q;Q.push(make_pair(-dp[gi][gj][k],make_pair(gi,gj)));while(!Q.empty()){int cur = - Q.top().first;auto [i,j] = Q.top().second;Q.pop();if(dp[i][j][k] < cur){continue;}for(int r = 0;r < 4;r++){int ni = i + d[r];int nj = j + d[r + 1];if(ni < 0 || nj < 0 || ni >= H || nj >= W){continue;}if(dp[ni][nj][k] > dp[i][j][k] + k * k + A[ni][nj]){dp[ni][nj][k] = dp[i][j][k] + k * k + A[ni][nj];Q.push(make_pair(-dp[ni][nj][k],make_pair(ni,nj)));}}}}int Q;cin >> Q;for(;Q--;){int x,y,k;cin >> x >> y >> k;x--; y--;long long ans = 0;if(k >= B){ans = (long long) k * k * (abs(x - gi) + abs(y - gj) + 1) + cost[x][y];}else{ans = dp[x][y][k];}cout << ans << "\n";}}int main(){ios::sync_with_stdio(false);cin.tie(nullptr);int tt = 1;/* cin >> tt; */while(tt--) Main();}