結果
問題 | No.867 避難経路 |
ユーザー | risujiroh |
提出日時 | 2019-08-16 23:08:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 5,076 ms / 6,000 ms |
コード長 | 2,690 bytes |
コンパイル時間 | 2,352 ms |
コンパイル使用メモリ | 191,580 KB |
実行使用メモリ | 29,996 KB |
最終ジャッジ日時 | 2024-09-22 21:48:48 |
合計ジャッジ時間 | 105,948 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
6,812 KB |
testcase_01 | AC | 2 ms
6,944 KB |
testcase_02 | AC | 2 ms
6,944 KB |
testcase_03 | AC | 2 ms
6,940 KB |
testcase_04 | AC | 2 ms
6,940 KB |
testcase_05 | AC | 2 ms
6,940 KB |
testcase_06 | AC | 2 ms
6,944 KB |
testcase_07 | AC | 2 ms
6,944 KB |
testcase_08 | AC | 2 ms
6,944 KB |
testcase_09 | AC | 2 ms
6,940 KB |
testcase_10 | AC | 2 ms
6,940 KB |
testcase_11 | AC | 3 ms
6,944 KB |
testcase_12 | AC | 2 ms
6,940 KB |
testcase_13 | AC | 2 ms
6,944 KB |
testcase_14 | AC | 2 ms
6,940 KB |
testcase_15 | AC | 2,028 ms
29,904 KB |
testcase_16 | AC | 2,293 ms
29,892 KB |
testcase_17 | AC | 2,172 ms
29,876 KB |
testcase_18 | AC | 2,009 ms
29,884 KB |
testcase_19 | AC | 1,901 ms
29,932 KB |
testcase_20 | AC | 402 ms
29,872 KB |
testcase_21 | AC | 371 ms
29,996 KB |
testcase_22 | AC | 550 ms
29,872 KB |
testcase_23 | AC | 622 ms
29,884 KB |
testcase_24 | AC | 548 ms
29,876 KB |
testcase_25 | AC | 5,071 ms
29,872 KB |
testcase_26 | AC | 5,065 ms
29,876 KB |
testcase_27 | AC | 5,070 ms
29,892 KB |
testcase_28 | AC | 5,076 ms
29,988 KB |
testcase_29 | AC | 5,070 ms
29,908 KB |
testcase_30 | AC | 5,054 ms
29,864 KB |
testcase_31 | AC | 5,059 ms
29,872 KB |
testcase_32 | AC | 5,068 ms
29,900 KB |
testcase_33 | AC | 5,056 ms
29,996 KB |
testcase_34 | AC | 5,061 ms
29,792 KB |
testcase_35 | AC | 5,060 ms
29,816 KB |
testcase_36 | AC | 5,064 ms
29,660 KB |
testcase_37 | AC | 5,062 ms
29,168 KB |
testcase_38 | AC | 5,059 ms
29,116 KB |
testcase_39 | AC | 5,055 ms
29,100 KB |
testcase_40 | AC | 5,063 ms
29,088 KB |
testcase_41 | AC | 2 ms
6,944 KB |
testcase_42 | AC | 2 ms
6,940 KB |
testcase_43 | AC | 2 ms
6,944 KB |
ソースコード
#include <bits/stdc++.h>using namespace std;using lint = long long;template<class T = int> using V = vector<T>;template<class T = int> using VV = V< V<T> >;using namespace chrono;auto start_t = steady_clock::now();void start() { start_t = steady_clock::now(); }int elapsed_time() { return duration_cast<milliseconds>(steady_clock::now() - start_t).count(); }struct Edge { int to; lint cost; };template<class T, class Edge> V<T> dijkstra(const VV<Edge>& g, int s = 0) {V<T> dist(g.size(), numeric_limits<T>::max());using P = pair<T, int>;priority_queue< P, V<P>, greater<P> > pque;pque.emplace(dist[s] = 0, s);while (!pque.empty()) {T d; int v;tie(d, v) = pque.top(); pque.pop();if (d > dist[v]) continue;for (const auto& e : g[v]) if (dist[v] + e.cost < dist[e.to]) {pque.emplace(dist[e.to] = dist[v] + e.cost, e.to);}}return dist;}int main() {cin.tie(nullptr); ios::sync_with_stdio(false);int h, w; cin >> h >> w;int gi, gj; cin >> gi >> gj, --gi, --gj;auto in = [&](int i, int j) -> int { return i * w + j; };auto out = [&](int i, int j) -> int { return (h + i) * w + j; };VV<Edge> g(2 * h * w);VV<> a(h, V<>(w));for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {cin >> a[i][j];g[in(i, j)].emplace_back(Edge{out(i, j), a[i][j]});for (int di = -1; di <= 1; ++di) for (int dj = -1; dj <= 1; ++dj) if (abs(di) + abs(dj) == 1) {int ni = i + di, nj = j + dj;if (ni < 0 or ni >= h or nj < 0 or nj >= w) continue;g[out(i, j)].emplace_back(Edge{in(ni, nj), 0});}}int q; cin >> q;struct Q { int t, i, j; lint k; };V<Q> qs(q);for (int t = 0; t < q; ++t) {qs[t].t = t;cin >> qs[t].i >> qs[t].j >> qs[t].k, --qs[t].i, --qs[t].j;}sort(begin(qs), end(qs), [](const auto& l, const auto& r) { return l.k < r.k; });V<lint> res(q);auto itr = begin(qs);while (itr != end(qs)) {lint k = itr->k;if (elapsed_time() >= 5000) {for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {g[in(i, j)][0].cost = a[i][j] + k * k;}auto d = dijkstra<lint>(g, in(gi, gj));while (itr != end(qs)) {int dist = abs(itr->i - gi) + abs(itr->j - gj) + 1;res[itr->t] = d[out(itr->i, itr->j)] + dist * (itr->k * itr->k - k * k);++itr;}break;}for (int i = 0; i < h; ++i) for (int j = 0; j < w; ++j) {g[in(i, j)][0].cost = a[i][j] + k * k;}auto d = dijkstra<lint>(g, in(gi, gj));while (itr != end(qs) and itr->k == k) {res[itr->t] = d[out(itr->i, itr->j)];++itr;}}for (lint e : res) cout << e << '\n';}