結果

問題 No.3013 ハチマキ買い星人
ユーザー kidodesu
提出日時 2025-01-25 12:48:34
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 823 ms / 2,000 ms
コード長 766 bytes
コンパイル時間 132 ms
コンパイル使用メモリ 82,644 KB
実行使用メモリ 139,376 KB
最終ジャッジ日時 2025-01-25 22:22:12
合計ジャッジ時間 19,610 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

n, m, p, y = map(int, input().split())
ABC = [tuple(map(int, input().split())) for _ in range(m)]
node = [[] for _ in range(n)]
for i in range(m):
	u, v, c = ABC[i]
	u, v = u-1, v-1
	node[u].append((v, c))
	node[v].append((u, c))
def dijk(start = 0):
    from heapq import heappop, heappush
    D = [float("INF") for _ in range(n)]
    hq = []
    heappush(hq, (0, start))
    D[start] = 0
    while hq:
        dist, now = heappop(hq)
        if D[now] < dist:
            continue
        for nxt, d in node[now]:
            if D[nxt] > D[now] + d:
                D[nxt] = D[now] + d
                heappush(hq, (D[nxt], nxt))
    return D
   
D = dijk()
ans = 0
for i in range(p):
	d, e = map(int, input().split())
	ans = max(ans, (y - D[d-1]) // e)
print(ans)
0