結果
問題 | No.1607 Kth Maximum Card |
ユーザー |
|
提出日時 | 2021-07-16 23:13:49 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 3,094 ms / 3,500 ms |
コード長 | 1,935 bytes |
コンパイル時間 | 990 ms |
コンパイル使用メモリ | 145,944 KB |
実行使用メモリ | 75,256 KB |
最終ジャッジ日時 | 2024-06-22 11:47:57 |
合計ジャッジ時間 | 41,607 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
import std.stdio, std.array, std.string, std.conv, std.algorithm; import std.typecons, std.range, std.random, std.math, std.container; import std.numeric, std.bigint, core.bitop, core.stdc.stdlib, std.datetime; void main() { auto s = readln.split.map!(to!int); auto N = s[0]; auto M = s[1]; auto K = s[2]; auto G = new Tuple!(int, int)[][](N); foreach (i; 0..M) { s = readln.split.map!(to!int); auto u = s[0] - 1; auto v = s[1] - 1; auto c = s[2]; G[u] ~= tuple(v, c); G[v] ~= tuple(u, c); } auto hi = 2 * 10 ^^5; auto lo = -1; while (hi - lo > 1) { auto mid = (hi + lo) / 2; if (search(N, M, K, G, mid)) { hi = mid; } else { lo = mid; } } hi.writeln; } bool search(int N, int M, int K, Tuple!(int, int)[][] G, int mid) { auto H = new Edge!(int)[][](N); foreach (i; 0..N) foreach (t; G[i]) { auto j = t[0]; auto c = t[1]; H[i] ~= Edge!(int)(j, (c <= mid ? 0 : 1)); } auto d = dijkstra!(int, 1 << 29)(H, 0)[N-1]; return d < K; } struct Edge(T) { int to; T cost; } T[] dijkstra(T, T inf)(const Edge!(T)[][] graph, int start) { import std.typecons : Tuple, tuple; import std.conv : to; import std.container : BinaryHeap; int n = graph.length.to!int; auto dist = new T[](n); dist[] = inf; dist[start] = 0; auto pq = new BinaryHeap!(Array!(Edge!(T)), "a.cost > b.cost"); pq.insert(Edge!(T)(start, 0)); while (!pq.empty) { auto u = pq.front.to; auto cost = pq.front.cost; pq.removeFront; foreach (const e; graph[u]) { auto v = e.to; auto next_cost = cost + e.cost; if (dist[v] <= next_cost) continue; dist[v] = next_cost; pq.insert(Edge!(T)(v, next_cost)); } } return dist; }