結果
問題 | No.1607 Kth Maximum Card |
ユーザー | titia |
提出日時 | 2021-07-24 05:53:30 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 746 bytes |
コンパイル時間 | 498 ms |
コンパイル使用メモリ | 86,632 KB |
実行使用メモリ | 134,324 KB |
最終ジャッジ日時 | 2023-09-26 11:30:58 |
合計ジャッジ時間 | 18,712 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge12 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 91 ms
71,380 KB |
testcase_01 | AC | 94 ms
71,216 KB |
testcase_02 | AC | 91 ms
71,432 KB |
testcase_03 | AC | 91 ms
71,584 KB |
testcase_04 | AC | 90 ms
71,560 KB |
testcase_05 | AC | 91 ms
71,328 KB |
testcase_06 | AC | 91 ms
71,168 KB |
testcase_07 | AC | 94 ms
71,536 KB |
testcase_08 | AC | 2,979 ms
134,324 KB |
testcase_09 | AC | 1,969 ms
118,084 KB |
testcase_10 | AC | 2,638 ms
131,896 KB |
testcase_11 | AC | 514 ms
90,088 KB |
testcase_12 | AC | 1,934 ms
118,624 KB |
testcase_13 | TLE | - |
testcase_14 | -- | - |
testcase_15 | -- | - |
testcase_16 | -- | - |
testcase_17 | -- | - |
testcase_18 | -- | - |
testcase_19 | -- | - |
testcase_20 | -- | - |
testcase_21 | -- | - |
testcase_22 | -- | - |
testcase_23 | -- | - |
testcase_24 | -- | - |
testcase_25 | -- | - |
testcase_26 | -- | - |
testcase_27 | -- | - |
testcase_28 | -- | - |
testcase_29 | -- | - |
testcase_30 | -- | - |
testcase_31 | -- | - |
testcase_32 | -- | - |
testcase_33 | -- | - |
testcase_34 | -- | - |
testcase_35 | -- | - |
ソースコード
import sys input = sys.stdin.readline from collections import deque N,M,K=map(int,input().split()) E=[[] for i in range(N)] for i in range(M): u,v,c=map(int,input().split()) u-=1 v-=1 E[u].append((v,c)) E[v].append((u,c)) OK=10**6 NG=0 while OK>NG+1: mid=(OK+NG)//2 Q=deque([0]) ANS=[1<<30]*N ANS[0]=0 while Q: x=Q.popleft() for to,c in E[x]: if c>=mid: if ANS[to]>ANS[x]+1: ANS[to]=ANS[x]+1 Q.append(to) else: if ANS[to]>ANS[x]: ANS[to]=ANS[x] Q.append(to) if ANS[N-1]>=K: NG=mid else: OK=mid print(NG)