結果

問題 No.1607 Kth Maximum Card
ユーザー SnowBeenDiding
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#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();
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0