結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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)
0