結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー Apollo@Kuro
提出日時 2025-01-21 19:24:17
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 1,134 bytes
コンパイル時間 345 ms
コンパイル使用メモリ 82,100 KB
実行使用メモリ 319,172 KB
最終ジャッジ日時 2025-01-25 22:01:14
合計ジャッジ時間 50,946 ms
ジャッジサーバーID
（参考情報） 		judge6 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 34 TLE * 11
権限があれば一括ダウンロードができます

ソースコード

diff # 

from collections import deque
import sys

# 入力を高速化
input = sys.stdin.read
def bfs(start, N, G, Y):
    dist = [-1] * (N + 1)
    dist[start] = Y
    que = deque([start])
    
    while que:
        pos = que.popleft()
        for to, cost in G[pos]:
            if dist[pos] >= cost and dist[pos] - cost > dist[to]:
                dist[to] = dist[pos] - cost
                que.append(to)
    
    return dist

def main():
    # 入力
    data = input().splitlines()
    N, M, P, Y = map(int, data[0].split())
    
    # グラフの初期化
    G = [[] for _ in range(N + 1)]
    edge_set = set()
    
    idx = 1
    for i in range(M):
        a, b, c = map(int, data[idx].split())
        G[a].append((b, c))
        G[b].append((a, c))
        edge_set.add((a, b))
        idx += 1
    
    # BFSの実行
    ret = bfs(1, N, G, Y)
    
    # 結果の計算
    ans = 0
    visited = set()
    for i in range(P):
        d, e = map(int, data[idx].split())
        visited.add(d)
        ans = max(ans, ret[d] // e)
        idx += 1
    
    # 結果を出力
    print(ans)

if __name__ == "__main__":
    main()
0