結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー Apollo@Kuro
提出日時 2025-01-21 19:24:17
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
TLE  
実行時間 -
コード長 1,134 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 273 ms
コンパイル使用メモリ 85,504 KB
実行使用メモリ 183,524 KB
最終ジャッジ日時 2026-06-23 19:46:00
合計ジャッジ時間 22,524 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 19 TLE * 1 -- * 25
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

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