結果
問題 | No.1473 おでぶなおばけさん |
ユーザー |
![]() |
提出日時 | 2021-04-04 18:20:18 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 109 ms / 2,000 ms |
コード長 | 1,283 bytes |
コンパイル時間 | 1,163 ms |
コンパイル使用メモリ | 89,812 KB |
最終ジャッジ日時 | 2025-01-20 11:25:41 |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 47 |
ソースコード
// 二分探索解 (AC) #include <algorithm> #include <iostream> #include <queue> #include <vector> using namespace std; int main() { cin.tie(nullptr), ios::sync_with_stdio(false); int N, M; cin >> N >> M; vector<vector<pair<int, int>>> to(N); vector<int> ds; for (int e = 0; e < M; e++) { int s, t, d; cin >> s >> t >> d; s--, t--; to[s].emplace_back(t, d); to[t].emplace_back(s, d); ds.push_back(d); } sort(ds.begin(), ds.end()); ds.erase(unique(ds.begin(), ds.end()), ds.end()); int ok = 0, ng = ds.size(); auto solve = [&](int th) -> int { vector<int> dist(N, 1 << 30); dist[0] = 0; queue<int> q; q.push(0); while (!q.empty()) { int now = q.front(); q.pop(); for (auto [nxt, w] : to[now]) { if (w >= th and dist[nxt] > dist[now] + 1) { dist[nxt] = dist[now] + 1; q.push(nxt); } } } return dist.back(); }; while (ng - ok > 1) { const int c = (ok + ng) / 2; auto ret = solve(ds[c]); (ret == 1 << 30 ? ng : ok) = c; } cout << ds[ok] << ' ' << solve(ds[ok]) << '\n'; }