結果
問題 | No.1607 Kth Maximum Card |
ユーザー |
![]() |
提出日時 | 2021-07-16 22:23:19 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,449 ms / 3,500 ms |
コード長 | 859 bytes |
コンパイル時間 | 293 ms |
コンパイル使用メモリ | 82,004 KB |
実行使用メモリ | 161,236 KB |
最終ジャッジ日時 | 2024-07-06 09:48:52 |
合計ジャッジ時間 | 16,525 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 33 |
ソースコード
from collections import deque def check(mid): # mid より大きい辺を使う最小回数 d = [1000000]*n d[0] = 0 q = deque() q.append((0,0)) while q: v,dist = q.popleft() if v==n-1: return d[v] if d[v] > dist: continue for u,c in g[v]: cost = int(c > mid) nd = d[v] + cost if nd < d[u]: d[u] = nd if cost: q.append((u,nd)) else: q.appendleft((u,nd)) return 1000000 import sys readline = sys.stdin.readline n,m,k = map(int,readline().split()) g = [[] for _ in range(n)] for _ in range(m): u,v,c = map(int,readline().split()) g[u-1].append((v-1,c)) g[v-1].append((u-1,c)) ng = -1 ok = 2*10**5+1 while ok-ng>1: mid = (ok+ng)//2 if check(mid) < k: ok = mid else: ng = mid print(ok)