結果
問題 | No.2354 Poor Sight in Winter |
ユーザー |
![]() |
提出日時 | 2023-06-16 21:55:14 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 36 ms / 2,000 ms |
コード長 | 1,327 bytes |
コンパイル時間 | 2,280 ms |
コンパイル使用メモリ | 201,036 KB |
最終ジャッジ日時 | 2025-02-14 05:22:57 |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 26 |
ソースコード
#include<bits/stdc++.h> using namespace std; int inf = 1001001001; bool chmin(int &x,int y) { if(x > y) { x = y; return true; } return false; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int N,K; cin >> N >> K; int sx,sy,gx,gy; cin >> sx >> sy >> gx >> gy; vector<int>x(N+2),y(N+2); for(int i = 0; i < N; i++) { cin >> x[i] >> y[i]; } x[N] = sx,y[N] = sy; x[N+1] = gx,y[N+1] = gy; int l = 0,r = 1001001; while(l+1 < r) { int mid = (l+r)/2; vector<int>dist(N+2,inf); dist[N] = 0; priority_queue<pair<int,int>,vector<pair<int,int>>,greater<pair<int,int>>>que; que.push({0,N}); while(!que.empty()) { pair<int,int>a = que.top(); que.pop(); if(dist[a.second] != a.first) continue; for(int i = 0; i < N+2; i++) { if(i == a.second) continue; int nxt = abs(x[a.second]-x[i])+abs(y[a.second]-y[i]); nxt = (nxt-1)/mid+a.first; if(chmin(dist[i],nxt)) { que.push({nxt,i}); } } } if(dist[N+1] <= K) { r = mid; } else { l = mid; } } cout << r << "\n"; }