結果
問題 |
No.1607 Kth Maximum Card
|
ユーザー |
![]() |
提出日時 | 2025-01-05 03:09:12 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,408 bytes |
コンパイル時間 | 3,908 ms |
コンパイル使用メモリ | 287,696 KB |
実行使用メモリ | 28,716 KB |
最終ジャッジ日時 | 2025-01-05 03:09:51 |
合計ジャッジ時間 | 32,888 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 31 TLE * 2 |
ソースコード
#include <bits/stdc++.h> #define rep(i, a, b) for (ll i = (ll)(a); i < (ll)(b); i++) using namespace std; typedef long long ll; template <typename T> struct Graph { struct edge { int to; T cost; }; int n; vector<vector<edge>> gr; vector<T> dist; vector<int> prever; Graph(int n) : n(n) { init(); } T inf() { return numeric_limits<T>::max(); } T zero() { return T(); } void init() { gr.resize(n); dist.resize(n, inf()); } void add_edge(int s, int t, T cost) { gr[s].emplace_back(edge{t, cost}); } void dijkstra(int s) { rep(i, 0, n) dist[i] = inf(); prever = vector<int>(n, -1); dist[s] = zero(); priority_queue<pair<T, int>, vector<pair<T, int>>, greater<pair<T, int>>> q; q.push({zero(), s}); while (!q.empty()) { int now; T nowdist; tie(nowdist, now) = q.top(); q.pop(); if (dist[now] < nowdist) continue; for (auto e : gr[now]) { T nextdist = nowdist + e.cost; // 次の頂点への距離 if (dist[e.to] > nextdist) { prever[e.to] = now; dist[e.to] = nextdist; q.push({dist[e.to], e.to}); } } } } void bfs01(int s) { rep(i, 0, n) dist[i] = inf(); prever = vector<int>(n, -1); dist[s] = zero(); deque<int> q; q.push_back(s); while (!q.empty()) { int now = q.front(); q.pop_front(); for (auto e : gr[now]) { T nextdist = dist[now] + e.cost; if (dist[e.to] > nextdist) { prever[e.to] = now; dist[e.to] = nextdist; if (e.cost == 0) q.push_front(e.to); else q.push_back(e.to); } } } } vector<int> get_path(int t) { // tへの最短路構築 if (dist[t] >= inf()) return {-1}; vector<int> path; for (; t != -1; t = prever[t]) { path.push_back(t); } reverse(path.begin(), path.end()); return path; } }; void solve() { int n, m, k; cin >> n >> m >> k; vector<int> u(m), v(m), c(m); rep(i, 0, m) { cin >> u[i] >> v[i] >> c[i]; u[i]--, v[i]--; } auto check = [&](ll mid) { // ([...,1,1,1,0,0,0,...]) Graph<int> gr(n); rep(i, 0, m) { if (c[i] > mid) { gr.add_edge(u[i], v[i], 1); gr.add_edge(v[i], u[i], 1); } else { gr.add_edge(u[i], v[i], 0); gr.add_edge(v[i], u[i], 0); } } gr.bfs01(0); return gr.dist[n - 1] >= k; }; auto binary = [&]() { ll L = -1, R = 1; while (check(R)) R *= 2; ll mid = L + (R - L) / 2; while (R - L > 1) { if (check(mid)) L = mid; else R = mid; mid = L + (R - L) / 2; } return R; }; cout << binary() << '\n'; } int main() { cin.tie(0); cout.tie(0); ios::sync_with_stdio(0); solve(); }