結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
![]() |
提出日時 | 2025-01-25 13:09:16 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,305 ms / 2,000 ms |
コード長 | 731 bytes |
コンパイル時間 | 338 ms |
コンパイル使用メモリ | 82,576 KB |
実行使用メモリ | 154,940 KB |
最終ジャッジ日時 | 2025-01-25 22:34:55 |
合計ジャッジ時間 | 27,694 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
import heapq N, M, P, Y = map(int, input().split()) edges = [list(map(int, input().split())) for _ in range(M)] shops = [list(map(int, input().split())) for _ in range(P)] C = 10**18 Cost = [C]*N graph = [[] for _ in range(N)] for a, b, c in edges: graph[b-1].append((a-1, c)) graph[a-1].append((b-1, c)) heap = [(0, 0)] Cost[0] = 0 visited = [False]*N while heap: c, x = heapq.heappop(heap) if visited[x]: continue visited[x] = True for u, c2 in graph[x]: if not visited[u] and c + c2 < Cost[u]: heapq.heappush(heap, [c+c2, u]) Cost[u] = c+c2 answer = 0 for d, e in shops: remain = max(Y-Cost[d-1], 0) answer = max(remain//e, answer) print(answer)