結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー matttttttoy
提出日時 2025-01-25 13:06:09
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 817 ms / 2,000 ms
コード長 772 bytes
コンパイル時間 171 ms
コンパイル使用メモリ 82,652 KB
実行使用メモリ 116,408 KB
最終ジャッジ日時 2025-01-25 22:33:16
合計ジャッジ時間 18,149 ms
ジャッジサーバーID
（参考情報） 		judge10 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

import heapq
N,M,P,Y=map(int,input().split())
graph=[[] for _ in range(N+1)]
for i in range(M):
    a,b,c=map(int,input().split())
    a-=1
    b-=1
    graph[a].append((b,c))
    graph[b].append((a,c))

def dijkstra(graphlist,start):
    INF=10**18
    flag=[0]*N
    cur=[INF]*N
    cur[start]=0
    Q=[(cur[start],start)]
    while Q:
        pos=heapq.heappop(Q)[1]
        if flag[pos]==1:
            continue

        flag[pos]=1
        for i in graphlist[pos]:
            next,cost=i
            if cur[next]>cur[pos]+cost:
                cur[next]=cur[pos]+cost
                heapq.heappush(Q,(cur[next],next))

    return cur

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