結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー Nichi10p
提出日時 2025-01-25 13:14:13
言語 Python3
(3.13.1 + numpy 2.2.1 + scipy 1.14.1)
結果
TLE  
実行時間 -
コード長 651 bytes
コンパイル時間 580 ms
コンパイル使用メモリ 12,288 KB
実行使用メモリ 159,104 KB
最終ジャッジ日時 2025-01-25 22:40:40
合計ジャッジ時間 72,462 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge11
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 27 TLE * 18
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heappush, heappop

def main():
  N, M, P, Y = map(int, input().split())
  G = [[] for _ in range(N)]
  V = [10**18 + 1] * N
  for _ in range(M):
    A, B, C = map(int, input().split())
    A -= 1
    B -= 1
    G[A].append((B, C))
    G[B].append((A, C))
  for _ in range(P):
    D, E = map(int, input().split())
    D -= 1
    V[D] = E

  D = [10**18] * N
  D[0] = 0
  pq = [(0, 0)]
  while pq:
    d, u = heappop(pq)
    if D[u] > d:
      continue
    for v, c in G[u]:
      if D[v] <= d+c:
        continue
      D[v] = d+c
      heappush(pq, (d+c, v))

  ans = max(max(Y-D[i], 0) // V[i] for i in range(N))
  print(ans)

main()
0