結果
問題 | No.867 避難経路 |
ユーザー |
![]() |
提出日時 | 2019-08-22 21:40:22 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 2,167 ms / 6,000 ms |
コード長 | 2,574 bytes |
コンパイル時間 | 734 ms |
コンパイル使用メモリ | 69,864 KB |
実行使用メモリ | 132,608 KB |
最終ジャッジ日時 | 2024-10-12 22:57:09 |
合計ジャッジ時間 | 61,379 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <iostream>#include <utility>#include <queue>#include <cstdlib>#define llint long long#define inf 1e18using namespace std;typedef pair<llint, llint> P;typedef pair<llint, P> S;llint h, w, Q;llint sx, sy;llint a[255][255];llint dist[255][255][255];llint dp[255][255];int dx[] = {1, 0, -1, 0}, dy[] = {0, -1, 0, 1};void dijkstra(llint k, llint dist[255][255]){for(int y = 1; y <= h; y++){for(int x = 1; x <= w; x++){dist[x][y] = inf;}}dist[sx][sy] = a[sx][sy]+k*k;priority_queue< S, vector<S>, greater<S> > Q;Q.push( make_pair(a[sx][sy]+k*k, make_pair(sx, sy)) );llint x, y, d, nx, ny;while(Q.size()){d = Q.top().first;x = Q.top().second.first, y = Q.top().second.second;Q.pop();if(dist[x][y] < d) continue;for(int i = 0; i < 4; i++){nx = x + dx[i], ny = y + dy[i];if(nx < 1 || nx > w || ny < 1 || ny > h) continue;if(dist[nx][ny] > d + a[nx][ny]+k*k){dist[nx][ny] = d + a[nx][ny]+k*k;Q.push( make_pair(dist[nx][ny], make_pair(nx, ny)) );}}}}int main(void){ios::sync_with_stdio(0);cin.tie(0);cin >> h >> w;cin >> sy >> sx;for(int y = 1; y <= h; y++){for(int x = 1; x <= w; x++){cin >> a[x][y];}}for(int i = 0; i < 255; i++) dijkstra(i, dist[i]);for(int x = 1; x <= w; x++){for(int y = 1; y <= h; y++){dp[x][y] = inf;}}dp[sx][sy] = a[sx][sy];for(int x = 0; sx+x <= w; x++){for(int y = 0; sy+y <= h; y++){int px = sx+x, py = sy+y;if(x > 0) dp[px][py] = min(dp[px][py], dp[px-1][py] + a[px][py]);if(y > 0) dp[px][py] = min(dp[px][py], dp[px][py-1] + a[px][py]);}}for(int x = 0; sx-x >= 1; x++){for(int y = 0; sy+y <= h; y++){int px = sx-x, py = sy+y;if(x > 0) dp[px][py] = min(dp[px][py], dp[px+1][py] + a[px][py]);if(y > 0) dp[px][py] = min(dp[px][py], dp[px][py-1] + a[px][py]);}}for(int x = 0; sx-x >= 1; x++){for(int y = 0; sy-y >= 1; y++){int px = sx-x, py = sy-y;if(x > 0) dp[px][py] = min(dp[px][py], dp[px+1][py] + a[px][py]);if(y > 0) dp[px][py] = min(dp[px][py], dp[px][py+1] + a[px][py]);}}for(int x = 0; sx+x <= w; x++){for(int y = 0; sy-y >= 1; y++){int px = sx+x, py = sy-y;if(x > 0) dp[px][py] = min(dp[px][py], dp[px-1][py] + a[px][py]);if(y > 0) dp[px][py] = min(dp[px][py], dp[px][py+1] + a[px][py]);}}cin >> Q;llint x, y, k;for(int q = 0; q < Q; q++){cin >> y >> x >> k;if(k <= 250) cout << dist[k][x][y] <<"\n";else cout << dp[x][y]+(abs(x-sx)+abs(y-sy)+1)*k*k << "\n";}flush(cout);return 0;}