結果
問題 | No.1607 Kth Maximum Card |
ユーザー |
|
提出日時 | 2021-07-16 21:49:24 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 531 ms / 3,500 ms |
コード長 | 882 bytes |
コンパイル時間 | 843 ms |
コンパイル使用メモリ | 81,388 KB |
実行使用メモリ | 17,760 KB |
最終ジャッジ日時 | 2024-07-06 08:51:49 |
合計ジャッジ時間 | 7,989 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
コンパイルメッセージ
main.cpp:43:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type] 43 | main() | ^~~~
ソースコード
#include<iostream> #include<vector> #include<deque> using namespace std; int N,M,K; vector<pair<int,int> >G[2<<17]; bool check(int L) { vector<int>dist(N,1e9); vector<bool>vis(N,false); dist[0]=0; deque<int>P; P.push_back(0); while(!P.empty()) { int u=P.front(); P.pop_front(); if(vis[u])continue; vis[u]=true; for(pair<int,int>e:G[u]) { int v=e.first; if(e.second>L) { if(dist[v]>dist[u]+1) { dist[v]=dist[u]+1; P.push_back(v); } } else { if(dist[v]>dist[u]) { dist[v]=dist[u]; P.push_front(v); } } } } return dist[N-1]<K; } main() { cin>>N>>M>>K; 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 L=-1,R=2e5; while(R-L>1) { int mid=(L+R)/2; if(check(mid))R=mid; else L=mid; } cout<<R<<endl; }