結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
|
提出日時 | 2023-06-16 22:36:08 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 80 ms / 2,000 ms |
コード長 | 1,666 bytes |
コンパイル時間 | 4,086 ms |
コンパイル使用メモリ | 257,348 KB |
最終ジャッジ日時 | 2025-02-14 06:38:49 |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
// #define _GLIBCXX_DEBUG #include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll = long long; #define rep(i,n) for (ll i = 0; i < (n); ++i) using vl = vector<ll>; using vvl = vector<vl>; using P = pair<ll,ll>; #define pb push_back #define int long long #define double long double #define INF (ll) 3e18 // Ctrl + Shift + B コンパイル // Ctrl + C 中断 // ./m 実行 signed main(){ int n, k; cin >> n >> k; int ok = 1000000; int ng = 0; int sx, sy, gx, gy; cin >> sx >> sy >> gx >> gy; vector<P> xy(n); rep(i,n) cin >> xy[i].first >> xy[i].second; xy.emplace_back(sx, sy); xy.emplace_back(gx, gy); n = xy.size(); vector<vector<P>> E(n); // 重み付きグラフへ rep(i,n){ rep(j,n){ if (i == j) continue; E[i].emplace_back(j, abs(xy[i].first-xy[j].first) + abs(xy[i].second-xy[j].second)); } } while(ok - ng != 1){ int mid = (ok + ng) / 2; priority_queue<P, vector<P>, greater<P>> pq; pq.emplace(0, n-2); vl dist(n, INF); dist[n-2] = 0; while(pq.size()){ auto [cost, now] = pq.top(); pq.pop(); if (dist[now] != cost) continue; for(auto [to, w] : E[now]){ if (dist[to] <= cost + (w-1) / mid) continue; dist[to] = cost + (w-1) / mid; pq.emplace(dist[to], to); } } if (dist[n-1] <= k) ok = mid; else ng = mid; } cout << ok << endl; } // 単に明かりを配置すればよいわけではなく // 例えば k = 2 (0,0) (6,6)なら // (3,3)においてはダメで、2,2 4,4 と配置する // Nが小さいので、視界で二分探索すればよいのではないか。