結果
問題 |
No.3013 ハチマキ買い星人
|
ユーザー |
![]() |
提出日時 | 2025-02-01 18:28:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 1,155 ms / 2,000 ms |
コード長 | 1,738 bytes |
コンパイル時間 | 265 ms |
コンパイル使用メモリ | 82,488 KB |
実行使用メモリ | 123,488 KB |
最終ジャッジ日時 | 2025-02-01 18:29:25 |
合計ジャッジ時間 | 27,554 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
from collections import deque, defaultdict, Counter from bisect import bisect_left, bisect_right from itertools import permutations, combinations from heapq import heappop, heappush import math _int = lambda x: int(x)-1 MOD = 998244353 INF = 1<<60 Yes, No = "Yes", "No" from heapq import heappop, heappush class Dijkstra: def __init__(self, n = 0): self._INF = 1<<60 self._n = n self._E = [[] for _ in range(self._n)] self.init_data() def init_data(self): self._cost = [self._INF]*self._n self._vis = [0]*self._n self._bf = [-1]*self._n def add_edge(self, u, v, c, directed = False): self._E[u].append((c, v)) if directed == False: self._E[v].append((c, u)) def calc(self, start): self.init_data() self._cost[start] = 0 q = [(0, start)] while q: cost, i = heappop(q) if self._vis[i]: continue self._vis[i] = 1 for c, j in self._E[i]: if self._vis[j]: continue if self._cost[j] < cost+c: continue self._cost[j] = cost+c self._bf[j] = i heappush(q, (cost+c, j)) def vis(self): return self._vis def cost(self): return self._cost def before(self): return self._bf N, M, P, Y = map(int, input().split()) D = Dijkstra(N) for _ in range(M): a, b, c = map(int, input().split()) D.add_edge(a-1, b-1, c) D.calc(0) vis = D.vis() cost = D.cost() ans = 0 for _ in range(P): d, e = map(int, input().split()) d = d-1 if vis[d] == 0: continue x = Y-cost[d] num = x//e ans = max(ans, num) print(ans)