結果
問題 | No.1607 Kth Maximum Card |
ユーザー |
|
提出日時 | 2021-12-11 00:39:37 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,119 bytes |
コンパイル時間 | 475 ms |
コンパイル使用メモリ | 82,396 KB |
実行使用メモリ | 376,484 KB |
最終ジャッジ日時 | 2024-07-18 21:30:14 |
合計ジャッジ時間 | 42,639 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 32 TLE * 1 |
ソースコード
N,M,K = map(int,input().split())board = []for _ in range(M):u,v,c = map(int,input().split())u-=1v-=1board.append((u,v,c))from collections import dequedef is_ok(x):edge = [[] for _ in range(N)]for i in range(M):u,v,c = board[i]if c > x:edge[u].append((v,1))edge[v].append((u,1))else:edge[u].append((v,0))edge[v].append((u,0))INF = float('inf')dis = [INF for _ in range(N)]q = deque()dis[0] = 0q.append((0,0))while q:t,now = q.popleft()if t > dis[now]:continuefor next,cost in edge[now]:if dis[next] > cost + dis[now]:dis[next] = cost + dis[now]if cost == 0:q.appendleft((dis[next],next))else:q.append((dis[next],next))if dis[N-1] <= K -1:return Trueelse:return Falseok = 2 * 10 ** 5ng = -1while ok - ng > 1:x = (ng+ok)//2if is_ok(x):ok = xelse:ng = xprint(ok)