結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
|
提出日時 | 2025-01-25 13:47:02 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 720 ms / 2,000 ms |
コード長 | 1,037 bytes |
コンパイル時間 | 451 ms |
コンパイル使用メモリ | 81,664 KB |
実行使用メモリ | 115,328 KB |
最終ジャッジ日時 | 2025-01-25 22:58:54 |
合計ジャッジ時間 | 16,429 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
import sys input = lambda: sys.stdin.readline().rstrip() import heapq def main(): # 入力 N, M, P, Y = map(int, input().split()) edges = [[] for _ in range(N)] for _ in range(M): A, B, C = map(int, input().split()) A, B = A - 1, B - 1 edges[A].append((B, C)) edges[B].append((A, C)) shop = [10**18+1]*N for _ in range(P): D, E = map(int, input().split()) shop[D-1] = E # 計算・出力 dist = [10**18]*N dist[0] = 0 hq = [(0, 0)] while hq: prevdist, prevnnode = heapq.heappop(hq) if dist[prevnnode] != prevdist: continue for nextnode, ddist in edges[prevnnode]: nextdist = prevdist + ddist if nextdist < dist[nextnode]: dist[nextnode] = nextdist heapq.heappush(hq, (nextdist, nextnode)) ans = 0 for i in range(N): nowY = Y - dist[i] res = nowY // shop[i] ans = max(ans, res) print(ans) if __name__ == "__main__": main()