結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
|
提出日時 | 2023-06-16 22:17:38 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 40 ms / 2,000 ms |
コード長 | 796 bytes |
コンパイル時間 | 2,193 ms |
コンパイル使用メモリ | 200,576 KB |
最終ジャッジ日時 | 2025-02-14 06:14:30 |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include <bits/stdc++.h> using namespace std; int main () { int N, K; cin >> N >> K; int X[555], Y[555]; for (int i = 0; i < N + 2; i ++) { cin >> X[i] >> Y[i]; } int ok = 2e5 + 5, ng = 0; using P = pair<int, int>; while (abs(ok - ng) > 1) { int mu = (ok + ng) / 2; vector<int> D(N + 2, 1e9 + 7); D[0] = 0; priority_queue<P, vector<P>, greater<P>> pque; pque.emplace(0, 0); while (!pque.empty()) { auto [l, u] = pque.top(); pque.pop(); if (l != D[u]) continue; for (int v = 1; v < N + 2; v ++) { if (u == v) continue; int d = abs(X[v] - X[u]) + abs(Y[v] - Y[u]); d = (d - 1) / mu; if (l + d < D[v]) { D[v] = l + d; pque.emplace(D[v], v); } } } if (D[1] <= K) { ok = mu; } else { ng = mu; } } cout << ok << endl; }