結果
問題 |
No.1607 Kth Maximum Card
|
ユーザー |
![]() |
提出日時 | 2023-11-18 04:47:25 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 866 ms / 3,500 ms |
コード長 | 1,279 bytes |
コンパイル時間 | 1,539 ms |
コンパイル使用メモリ | 117,020 KB |
実行使用メモリ | 16,512 KB |
最終ジャッジ日時 | 2024-09-26 05:39:38 |
合計ジャッジ時間 | 11,421 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
#include<algorithm> #include<iostream> #include<vector> #include<map> #include<cassert> #include<set> #include<queue> using namespace std; using ll = long long; int main(){ cin.tie(nullptr); ios::sync_with_stdio(false); int n,m,k; cin>>n>>m>>k; vector<vector<pair<int,int>>> g(n); for(int i = 0;i<m;i++){ int u,v,c; cin>>u>>v>>c; u--;v--; g[u].push_back(make_pair(v,c)); g[v].push_back(make_pair(u,c)); } int right = 2<<17; int left = -1; while(right-left>1){ int mid = (right+left) / 2; deque<int> que; vector<int> can(n,1e9); vector<int> vis(n,0); can[0] = 0; que.push_back(0); while(que.size()){ auto ni = que.front(); que.pop_front(); if(vis[ni]++) continue; for(auto&itr:g[ni]){ int need = can[ni]; if(itr.second>mid) need++; if(vis[itr.first]) continue; if(need==can[ni]) que.push_front(itr.first); else que.push_back(itr.first); can[itr.first] = min(can[itr.first],need); } } if(can[n-1]<k) right = mid; else left = mid; } cout<<right<<endl; }