結果
問題 | No.3013 ハチマキ買い星人 |
ユーザー |
![]() |
提出日時 | 2025-01-25 13:58:17 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,716 ms / 2,000 ms |
コード長 | 961 bytes |
コンパイル時間 | 400 ms |
コンパイル使用メモリ | 82,388 KB |
実行使用メモリ | 175,120 KB |
最終ジャッジ日時 | 2025-01-25 23:04:26 |
合計ジャッジ時間 | 32,313 ms |
ジャッジサーバーID (参考情報) |
judge8 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
from heapq import heapify,heappush, heappop def dijkstra(G, s): INF = 10**18 dist = [[INF,INF] for _ in range(N)] dist[s][0] = 0 pq = [(0, s, 10**18)] heapify(pq) while pq: d, v, c = heappop(pq) if d > dist[v][0]: continue for u, weight in G[v]: nd = d + weight if dist[u][0] > nd: dist[u][0] = nd m = 10**18 if u in D: m = D[u] dist[u][1] = min(dist[u][1],m) heappush(pq, (nd, u, min(c,m))) return dist N,M,P,Y = map(int,input().split()) G = [set() for _ in range(N)] for _ in range(M): a,b,c = map(int,input().split()) a,b = a-1,b-1 G[a].add((b,c)) G[b].add((a,c)) D = dict() for _ in range(P): d,e = map(int,input().split()) D[d-1] = e L = dijkstra(G,0) if 0 in D: L[0][1] = D[0] Ans = 0 for c,m in L: Ans = max(Ans,(Y-c)//m) print(Ans)