結果
問題 |
No.1607 Kth Maximum Card
|
ユーザー |
![]() |
提出日時 | 2023-06-11 00:54:11 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 3,409 ms / 3,500 ms |
コード長 | 1,478 bytes |
コンパイル時間 | 1,384 ms |
コンパイル使用メモリ | 116,516 KB |
最終ジャッジ日時 | 2025-02-14 01:26:45 |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include <iostream> #include <vector> #include <cmath> #include <map> #include <set> #include <iomanip> #include <queue> #include <algorithm> #include <numeric> #include <deque> #include <complex> #include <cassert> using namespace std; using ll = long long; ll N, M, K; vector<ll> u, v, c; vector<int> zobfs(vector<vector<pair<int, int>>> &E, int start){ int N = E.size(); int from, to, alt; deque<int> que; vector<int> dist(N, 1e9); dist[start] = 0; que.push_back(start); while(!que.empty()){ from = que.front(); que.pop_front(); for (auto [to, C] : E[from]){ alt = dist[from]+C; if (alt < dist[to]){ dist[to] = alt; if (C) que.push_back(to); else que.push_front(to); } } } return dist; } bool solve(ll X){ int A, B, C; vector<vector<pair<int, int>>> E(N); for (int i=0; i < M; i++){ A = u[i]; B = v[i]; C = (c[i] > X ? 1 : 0); E[A].push_back({B, C}); E[B].push_back({A, C}); } vector<int> dist = zobfs(E, 0); return dist[N-1] < K; } int main(){ cin >> N >> M >> K; u.resize(M); v.resize(M); c.resize(M); for (int i=0; i<M; i++){ cin >> u[i] >> v[i] >> c[i]; u[i]--; v[i]--; } ll l=-1, r=2e5, c; while(r-l>1){ c = (l+r)/2; if (solve(c)) r=c; else l=c; } cout << r << endl; }