結果

問題 No.2387 Yokan Factory
ユーザー rin204
提出日時 2024-04-07 15:01:06
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,160 ms / 5,000 ms
コード長 871 bytes
コンパイル時間 221 ms
コンパイル使用メモリ 82,516 KB
実行使用メモリ 128,012 KB
最終ジャッジ日時 2024-10-01 04:30:55
合計ジャッジ時間 12,788 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 35
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappop, heappush

n, m, T = map(int, input().split())

B = [-1]
edges = [[] for _ in range(n)]
for _ in range(m):
    u, v, a, b = map(int, input().split())
    u -= 1
    v -= 1
    edges[u].append((v, a, b))
    edges[v].append((u, a, b))
    B.append(b)


def ok(x):
    dist = [T + 1] * n
    dist[0] = 0
    hq = [0]
    while hq:
        tmp = heappop(hq)
        d = tmp // n
        pos = tmp - d * n
        if dist[pos] < d:
            continue
        for npos, a, b in edges[pos]:
            if b < x:
                continue
            nd = d + a
            if nd < dist[npos]:
                dist[npos] = nd
                heappush(hq, nd * n + npos)
    return dist[n - 1] <= T


B = sorted(set(B))
l = 0
r = len(B)
while r - l > 1:
    mid = (l + r) // 2
    if ok(B[mid]):
        l = mid
    else:
        r = mid

print(B[l])
0