結果
問題 | 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(); }