結果
問題 | 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);elseq.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;elseR = 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();}