結果
問題 | No.867 避難経路 |
ユーザー |
|
提出日時 | 2019-09-06 00:57:06 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 1,842 ms / 6,000 ms |
コード長 | 3,000 bytes |
コンパイル時間 | 1,707 ms |
コンパイル使用メモリ | 180,116 KB |
実行使用メモリ | 103,424 KB |
最終ジャッジ日時 | 2024-06-23 01:22:04 |
合計ジャッジ時間 | 49,312 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 41 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;const int dx[] = {1, -1, 0, 0};const int dy[] = {0, 0, 1, -1};const ll INF = 1e16;ll a[251][251];struct State {int x;int y;ll cost;//int prev;State(int x, int y, ll cost/*, int prev*/) : x(x), y(y), cost(cost)/*, prev(prev)*/ {}bool operator>(const State& s) const {//if (cost != s.cost) return cost > s.cost;//if (prev != s.prev) return prev > s.prev; //最短経路を辞書順最小にする(省略可)//return at > s.at;return cost > s.cost;}};//const int NONE = -1;//sは始点、mincは最短経路のコスト、Prevは最短経路をたどる際の前の頂点void dijkstra(int sx, int sy, ll k, int H, int W, vector< vector<ll> >& minc/*, vector<int>& Prev*/){minc.assign(H, vector<ll>(W, INF));//Prev.assign(graph.size(), INF);priority_queue<State, vector<State>, greater<State> > pq;pq.emplace(sx, sy, k + a[sx][sy]/*, NONE*/);while(!pq.empty()) {State cur = pq.top();pq.pop();if (minc[cur.x][cur.y] <= cur.cost) continue;minc[cur.x][cur.y] = cur.cost;//Prev[cur.at] = cur.prev;for (int i = 0; i < 4; i++) {int nx = cur.x + dx[i], ny = cur.y + dy[i];if (nx < 0 || nx >= H || ny < 0 || ny >= W) continue;ll cost = cur.cost + a[nx][ny] + k;if (minc[nx][ny] <= cost) continue;pq.emplace(nx, ny, cost);}}}ll dp[251][251];void calc(int x, int y, int dirx, int diry, int H, int W) {int nx = x + dirx;if (nx >= 0 && nx < H) {dp[nx][y] = min(dp[nx][y], dp[x][y] + a[nx][y]);calc(nx, y, dirx, diry, H, W);}int ny = y + diry;if (ny >= 0 && ny < W) {dp[x][ny] = min(dp[x][ny], dp[x][y] + a[x][ny]);}}void solve(int x, int y, int dirx, int diry, int H, int W) {while (y >= 0 && y < W) {calc(x, y, dirx, diry, H, W);y += diry;}}int main() {cin.tie(0);ios::sync_with_stdio(false);int H, W, gx, gy;cin >> H >> W >> gx >> gy;gx--; gy--;for (int i = 0; i < H; i++) {for (int j = 0; j < W; j++) {cin >> a[i][j];dp[i][j] = INF;}}dp[gx][gy] = a[gx][gy];solve(gx, gy, 1, 1, H, W);solve(gx, gy, 1, -1, H, W);solve(gx, gy, -1, 1, H, W);solve(gx, gy, -1, -1, H, W);constexpr ll K_SMALL = 200;vector< vector< vector<ll> > > mincs(K_SMALL);for (ll k = 1; k < K_SMALL; k++) {dijkstra(gx, gy, k * k, H, W, mincs[k]);}int q;cin >> q;for (int i = 0; i < q; i++) {int x, y;ll k;cin >> x >> y >> k;x--; y--;if (k >= K_SMALL) {k *= k;cout << k * (abs(x - gx) + abs(y - gy) + 1) + dp[x][y] << "\n";} else {cout << mincs[k][x][y] << "\n";}}return 0;}