結果
問題 |
No.1607 Kth Maximum Card
|
ユーザー |
![]() |
提出日時 | 2021-07-20 19:00:00 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 645 ms / 3,500 ms |
コード長 | 1,792 bytes |
コンパイル時間 | 1,140 ms |
コンパイル使用メモリ | 104,252 KB |
実行使用メモリ | 16,580 KB |
最終ジャッジ日時 | 2024-07-17 13:45:58 |
合計ジャッジ時間 | 7,546 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
/* -*- coding: utf-8 -*- * * 1607.cc: No.1607 Kth Maximum Card - yukicoder */ #include<cstdio> #include<cstdlib> #include<cstring> #include<cmath> #include<iostream> #include<string> #include<vector> #include<map> #include<set> #include<stack> #include<list> #include<queue> #include<deque> #include<algorithm> #include<numeric> #include<utility> #include<complex> #include<functional> using namespace std; /* constant */ const int MAX_N = 200000; const int INF = 1 << 30; /* typedef */ typedef long long ll; typedef queue<int> qi; typedef pair<int,int> pii; typedef vector<pii> vpii; /* global variables */ vpii nbrs[MAX_N]; int ds[MAX_N]; bool used[MAX_N]; /* subroutines */ int bfs01(int n, int x) { fill(ds, ds + n, INF); fill(used, used + n, false); ds[0] = 0; qi q0, q1; q0.push(0); while (! q0.empty() || ! q1.empty()) { if (q0.empty()) swap(q0, q1); int u = q0.front(); q0.pop(); if (used[u]) continue; if (u == n - 1) break; used[u] = true; for (auto vc: nbrs[u]) { int v = vc.first; int vd = ds[u] + (vc.second <= x ? 0 : 1); if (ds[v] > vd) { ds[v] = vd; (vc.second <= x ? q0 : q1).push(v); } } } //for (int i = 0; i < n; i++) printf(" %d", ds[i]); putchar('\n'); //printf("bfs01(%d, %d) = %d\n", n, x, ds[n - 1]); return ds[n - 1]; } /* main */ int main() { int n, m, k; scanf("%d%d%d", &n, &m, &k); int maxc = 0; for (int i = 0; i < m; i++) { int u, v, c; scanf("%d%d%d", &u, &v, &c); u--, v--; nbrs[u].push_back(pii(v, c)); nbrs[v].push_back(pii(u, c)); maxc = max(maxc, c); } int x0 = -1, x1 = maxc; while (x0 + 1 < x1) { int x = (x0 + x1) / 2; if (bfs01(n, x) >= k) x0 = x; else x1 = x; } printf("%d\n", x1); return 0; }