結果
問題 | No.1607 Kth Maximum Card |
ユーザー |
![]() |
提出日時 | 2025-01-05 02:56:24 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 3,110 bytes |
コンパイル時間 | 4,107 ms |
コンパイル使用メモリ | 291,992 KB |
実行使用メモリ | 29,408 KB |
最終ジャッジ日時 | 2025-01-05 02:56:59 |
合計ジャッジ時間 | 30,294 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
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>> G;vector<T> dist;vector<int> prever;Graph(int n) { init(n); }T inf() {if (is_same_v<T, int>)return 1e9;elsereturn 1e18;}T zero() { return T(0); }void init(int n) {N = n;G.resize(N);dist.resize(N, inf());}void add_edge(int s, int t, T cost) {edge e;e.to = t, e.cost = cost;G[s].push_back(e);}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 : G[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});}}}}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]--;}int q = 1;while (q--) {int s = 0, t = n - 1;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.dijkstra(s);return gr.dist[t] >= k;};auto binary = [&]() { // llll L = -1, R = 1; // 解[L,R) 探索範囲(L,R)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; // L-true R-false};cout << binary() << ' ';}cout << '\n';}int main() {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);solve();}