結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
![]() |
提出日時 | 2023-06-17 00:35:19 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 62 ms / 2,000 ms |
コード長 | 1,396 bytes |
コンパイル時間 | 3,162 ms |
コンパイル使用メモリ | 257,824 KB |
実行使用メモリ | 5,608 KB |
最終ジャッジ日時 | 2024-06-24 17:37:31 |
合計ジャッジ時間 | 4,621 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h>using namespace std;using ll = long long;ll INF = 1LL << 58;#define pb push_backtemplate<typename T> using min_priority_queue = priority_queue<T, vector<T>, greater<T>>;int main() {ll N, K; cin >> N >> K;ll sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy;vector<ll> X(N), Y(N);for (int i = 0; i < N; i++) {cin >> X[i] >> Y[i];}// N -> s, N + 1 -> gX.pb(sx); X.pb(gx);Y.pb(sy); Y.pb(gy);auto check = [&](ll P) -> bool {vector cost(N + 2, vector<ll>(N + 2));for (int i = 0; i < N + 2; i++) {for (int j = i; j < N + 2; j++) {ll m = abs(X[i] - X[j]) + abs(Y[i] - Y[j]);if (m == 0) m++;cost[i][j] = (m - 1) / P;cost[j][i] = (m - 1) / P;}}vector<ll> dist(N + 2, INF);min_priority_queue<pair<ll, ll>> que;que.push({0, N});dist[N] = 0;while (!que.empty()) {auto [d, i] = que.top(); que.pop();if (dist[i] != d) continue;for (int j = 0; j < N + 2; j++) {ll nv = dist[i] + cost[i][j];if (dist[j] > nv) {dist[j] = nv;que.push({nv, j});}}}return dist[N + 1] <= K;};ll ok = 101010, ng = 0;while (abs(ok - ng) > 1) {ll mid = (ok + ng) / 2;if (check(mid)) {ok = mid;} else {ng = mid;}}cout << ok << endl;}