結果

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

ソースコード

diff #
raw source code 

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