結果

問題 No.3013 ハチマキ買い星人
ユーザー miya256
提出日時 2025-01-25 13:32:08
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,165 ms / 2,000 ms
コード長 1,613 bytes
コンパイル時間 226 ms
コンパイル使用メモリ 81,792 KB
実行使用メモリ 128,240 KB
最終ジャッジ日時 2025-01-25 22:50:40
合計ジャッジ時間 25,439 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

from heapq import heapify,heappush,heappop

class Dijkstra:
    INF = 1<<61

    def __init__(self,g):
        """隣接リストor頂点数"""
        if isinstance(g,int):
            g = [[] for _ in range(g)]
        self.n = len(g)
        self.g = g
        self.prev = [-1] * self.n
    
    def add_edge(self,u,v,w,isDirected=None):
        assert isDirected is not None, "有向辺かどうかを確かめてください"
        self.g[u].append((v,w))
        if not isDirected:
            self.g[v].append((u,w))
    
    def dijkstra(self,start):
        """startからの最短距離"""
        self.prev = [-1] * self.n
        visited = [False] * self.n
        dist = [self.INF] * self.n
        hq = [(0,start,-1)]
        dist[start] = 0
        while hq:
            d,v,prev = heappop(hq)
            if visited[v]:
                continue
            visited[v] = True
            self.prev[v] = prev
            for nv,w in self.g[v]:
                if dist[nv] > d+w:
                    dist[nv] = d+w
                    heappush(hq,(dist[nv],nv,v))
        return dist
    
    def get_path(self,u,v):
        """直前にuからの最短距離を求めた場合、u->vの経路を復元"""
        path = [v]
        while path[-1] != u:
            path.append(self.prev[path[-1]])
        return path[::-1]

n,m,p,y = map(int,input().split())
g = Dijkstra(n)
for _ in range(m):
    a,b,c = map(int,input().split())
    g.add_edge(a-1,b-1,c,False)
dist = g.dijkstra(0)
ans = 0

for _ in range(p):
    d,e = map(int,input().split())
    ans = max(ans, (y-dist[d-1]) // e)
print(ans)
0