結果

問題 No.1607 Kth Maximum Card
ユーザー 👑 tamatotamato
提出日時 2021-07-16 22:15:35
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 2,723 ms / 3,500 ms
コード長 1,341 bytes
コンパイル時間 354 ms
コンパイル使用メモリ 87,348 KB
実行使用メモリ 195,296 KB
最終ジャッジ日時 2023-09-20 14:24:46
合計ジャッジ時間 29,974 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 92 ms
72,004 KB
testcase_01 AC 92 ms
71,724 KB
testcase_02 AC 92 ms
72,128 KB
testcase_03 AC 93 ms
71,728 KB
testcase_04 AC 94 ms
72,016 KB
testcase_05 AC 91 ms
71,976 KB
testcase_06 AC 92 ms
71,984 KB
testcase_07 AC 93 ms
71,864 KB
testcase_08 AC 1,651 ms
165,684 KB
testcase_09 AC 983 ms
142,072 KB
testcase_10 AC 1,947 ms
179,612 KB
testcase_11 AC 277 ms
96,468 KB
testcase_12 AC 1,750 ms
155,080 KB
testcase_13 AC 340 ms
89,764 KB
testcase_14 AC 416 ms
93,932 KB
testcase_15 AC 1,371 ms
151,240 KB
testcase_16 AC 321 ms
90,796 KB
testcase_17 AC 190 ms
81,784 KB
testcase_18 AC 905 ms
125,952 KB
testcase_19 AC 576 ms
104,432 KB
testcase_20 AC 726 ms
112,028 KB
testcase_21 AC 802 ms
117,340 KB
testcase_22 AC 1,406 ms
169,552 KB
testcase_23 AC 1,480 ms
169,528 KB
testcase_24 AC 743 ms
102,504 KB
testcase_25 AC 503 ms
93,216 KB
testcase_26 AC 641 ms
96,212 KB
testcase_27 AC 849 ms
104,200 KB
testcase_28 AC 644 ms
98,184 KB
testcase_29 AC 1,528 ms
130,916 KB
testcase_30 AC 2,723 ms
169,636 KB
testcase_31 AC 1,424 ms
124,200 KB
testcase_32 AC 430 ms
139,744 KB
testcase_33 AC 469 ms
146,916 KB
testcase_34 AC 693 ms
195,296 KB
testcase_35 AC 670 ms
191,520 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

mod = 1000000007
eps = 10**-9
L = 2*10**5
LL = L+1


def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    N, M, K = map(int, input().split())
    ABC = []
    adj = [[] for _ in range(N+1)]
    C = []
    for i in range(M):
        a, b, c = map(int, input().split())
        ABC.append((a, b, c))
        adj[a].append((b, i))
        adj[b].append((a, i))
        C.append(c)

    ok = L
    ng = -1
    mid = (ok + ng) // 2
    C01 = [0] * M
    while ok - ng > 1:
        for i, c in enumerate(C):
            if c > mid:
                C01[i] = 1
            else:
                C01[i] = 0

        que = deque()
        que.append(LL)
        seen = [-1] * (N+1)
        while que:
            vd = que.popleft()
            v, d = divmod(vd, LL)
            if seen[v] != -1:
                continue
            seen[v] = d
            if v == N:
                break
            for u, i in adj[v]:
                c = C01[i]
                if seen[u] == -1:
                    if c:
                        que.append(u * LL + d + 1)
                    else:
                        que.appendleft(u * LL + d)
        if seen[N] < K:
            ok = mid
        else:
            ng = mid
        mid = (ok + ng) // 2
    print(ok)


if __name__ == '__main__':
    main()
0