結果
問題 | 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;}