結果

問題 No.3013 ハチマキ買い星人
コンテスト
ユーザー Apollo@Kuro
提出日時 2024-12-31 08:45:24
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 1,782 ms / 2,000 ms
コード長 5,453 bytes
コンパイル時間 705 ms
コンパイル使用メモリ 82,688 KB
実行使用メモリ 159,844 KB
最終ジャッジ日時 2025-01-25 22:12:23
合計ジャッジ時間 26,078 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 45
権限があれば一括ダウンロードができます

ソースコード

diff # 

def main():
    
    N, M, P, Y = map(int, input().split())
    graph = defaultdict(list)
    
    for _ in range(M):
        A, B, C = map(int, input().split())
        graph[A].append((B, C))
        graph[B].append((A, C))
    
    shops = [tuple(map(int, input().split())) for _ in range(P)]
    
    def dijkstra(start):
        dist = {i: float('inf') for i in range(1, N + 1)}
        dist[start] = 0
        pq = SortedList([(0, start)])
        
        while pq:
            current_cost, current_node = pq.pop(0)
            if current_cost > dist[current_node]:
                continue
            
            for neighbor, cost in graph[current_node]:
                new_cost = current_cost + cost
                if new_cost < dist[neighbor]:
                    if dist[neighbor] != float('inf'):
                        pq.discard((dist[neighbor], neighbor))
                    dist[neighbor] = new_cost
                    pq.add((new_cost, neighbor))
        
        return dist
    
    min_cost = dijkstra(1)
    
    max_hachimaki = 0
    for D, E in shops:
        if min_cost[D] <= Y:
            max_hachimaki = max((Y - min_cost[D]) // E, max_hachimaki)
            
    print(max_hachimaki)
    
    
    pass

""""""""""""""""""""""""""
##########################
""""""""""""""""""""""""""

from heapq import *
from bisect import *
from collections import * 

import sys
sys.setrecursionlimit(10**9)
sys.set_int_max_str_digits(0)

class SortedList:
    def __init__(self, iterable=None):
        self._list = []
        self._min = None  # 最小値のキャッシュ
        self._max = None  # 最大値のキャッシュ
        if iterable:
            self.update(iterable)

    def add(self, value):
        """値を追加してソートを維持します"""
        insort(self._list, value)
        if self._min is None or value < self._min:
            self._min = value
        if self._max is None or value > self._max:
            self._max = value

    def remove(self, value):
        index = bisect_left(self._list, value)
        if index < len(self._list) and self._list[index] == value:
            self._list.pop(index)
            if value == self._min or value == self._max:
                self._min = self._list[0] if self._list else None
                self._max = self._list[-1] if self._list else None
        else:
            raise ValueError(f"{value} is not in list")

    def discard(self, value):
        index = bisect_left(self._list, value)
        if index < len(self._list) and self._list[index] == value:
            self._list.pop(index)
            if value == self._min or value == self._max:
                self._min = self._list[0] if self._list else None
                self._max = self._list[-1] if self._list else None

    def __contains__(self, value):
        """値がリストに含まれているかを確認します"""
        index = bisect_left(self._list, value)
        return index < len(self._list) and self._list[index] == value

    def __len__(self):
        """リストの長さを返します"""
        return len(self._list)

    def __getitem__(self, index):
        """指定したインデックスの値を取得します"""
        return self._list[index]

    def __delitem__(self, index):
        value = self._list[index]
        del self._list[index]
        if value == self._min or value == self._max:
            self._min = self._list[0] if self._list else None
            self._max = self._list[-1] if self._list else None

    def __iter__(self):
        return iter(self._list)

    def __repr__(self):
        return f"SortedList({self._list})"

    def bisect_left(self, value):
        return bisect_left(self._list, value)

    def bisect_right(self, value):
        return bisect_right(self._list, value)

    def index(self, value):
        index = bisect_left(self._list, value)
        if index < len(self._list) and self._list[index] == value:
            return index
        else:
            raise ValueError(f"{value} is not in list")

    def pop(self, index=-1):
        value = self._list.pop(index)
        if value == self._min or value == self._max:
            self._min = self._list[0] if self._list else None
            self._max = self._list[-1] if self._list else None
        return value

    def clear(self):
        self._list.clear()
        self._min = None
        self._max = None

    def extend(self, iterable):
        for value in iterable:
            self.add(value)

    def update(self, iterable):
        for value in iterable:
            self.add(value)

    def min(self):
        if self._min is None:
            raise ValueError("The list is empty")
        return self._min

    def max(self):
        if self._max is None:
            raise ValueError("The list is empty")
        return self._max

    def range(self, start, stop):
        left = self.bisect_left(start)
        right = self.bisect_left(stop)
        return self._list[left:right]

    def count(self, value):
        return self.bisect_right(value) - self.bisect_left(value)

    def index_range(self, start, stop):
        left = self.bisect_left(start)
        right = self.bisect_left(stop)
        return range(left, right)

    def find_kth(self, k):
        if 0 <= k < len(self._list):
            return self._list[k]
        raise IndexError("Index out of range")

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