結果
問題 |
No.2897 2集合間距離
|
ユーザー |
![]() |
提出日時 | 2024-09-21 01:17:35 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 215 ms / 3,500 ms |
コード長 | 1,222 bytes |
コンパイル時間 | 3,206 ms |
コンパイル使用メモリ | 252,968 KB |
実行使用メモリ | 14,180 KB |
最終ジャッジ日時 | 2024-09-21 01:17:42 |
合計ジャッジ時間 | 6,220 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 24 |
ソースコード
#include <bits/stdc++.h> using namespace std; vector<int> di = {-1, 0, 1, 0}; vector<int> dj = {0, 1, 0, -1}; int H = 1010, W = 1010, INF = 2000000000; int main() { int n; cin >> n; vector<int> x(n), y(n); for (int i = 0; i < n; i++) { cin >> x[i] >> y[i]; } int m; cin >> m; vector<int> z(m), w(m); for (int i = 0; i < m; i++) { cin >> z[i] >> w[i]; } auto inc = [&](int i, int j) { return (0 <= i && i < H && 0 <= j && j < W); }; vector<int> dist(H * W, INF); queue<pair<int, int>> q; for (int i = 0; i < n; i++) { dist[W * x[i] + y[i]] = 0; q.emplace(x[i], y[i]); } while (!q.empty()) { auto [i, j] = q.front(); q.pop(); for (int k = 0; k < 4; k++) { int ni = i + di[k], nj = j + dj[k]; if (!inc(ni, nj)) { continue; } if (dist[W * ni + nj] > dist[W * i + j] + 1) { dist[W * ni + nj] = dist[W * i + j] + 1; q.emplace(ni, nj); } } } int ans = INF; for (int i = 0; i < m; i++) { ans = min(ans, dist[W * z[i] + w[i]]); } cout << ans << endl; }