結果
問題 |
No.3013 ハチマキ買い星人
|
ユーザー |
![]() |
提出日時 | 2025-09-06 10:22:56 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 987 ms / 2,000 ms |
コード長 | 1,641 bytes |
コンパイル時間 | 347 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 148,656 KB |
最終ジャッジ日時 | 2025-09-06 10:23:23 |
合計ジャッジ時間 | 24,943 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 45 |
ソースコード
import heapq def dijkstra(graph, start): distances = [float('inf') for _ in range(len(graph))] distances[start] = 0 queue = [(0, start)] while queue: current_distance, current_node = heapq.heappop(queue) if current_distance > distances[current_node]: continue for neighbor, weight in graph[current_node]: distance = current_distance + weight if distance < distances[neighbor]: distances[neighbor] = distance heapq.heappush(queue, (distance, neighbor)) return distances from heapq import heappop, heappush, heapify from bisect import bisect #from sortedcontainers import SortedList from collections import deque, defaultdict from math import floor, ceil, isqrt, comb from sys import stdin, setrecursionlimit #setrecursionlimit(10**7) intin = lambda: int(stdin.readline()) strin = lambda: stdin.readline().rstrip() listin = lambda: list(map(int, stdin.readline().split())) tuplein = lambda m: [tuple(map(lambda x: int(x) if x.isdigit() or (len(x) > 1 and x[0] == "-" and x[1:].isdigit()) else x, stdin.readline().split())) for _ in range(m)] gridin = lambda m: [list(map(int, stdin.readline().split())) for _ in range(m)] strgridin = lambda h: [stdin.readline().rstrip() for _ in range(h)] mapin = lambda: map(int, stdin.readline().split()) N, M, P, Y = mapin() ABC = tuplein(M) DE = tuplein(P) graph = [[] for _ in range(N)] for a, b, c in ABC: a -= 1; b -= 1 graph[a].append((b, c)) graph[b].append((a, c)) dst = dijkstra(graph, 0) ans = 0 for d, e in DE: d -= 1 ans = max(ans, (Y - dst[d]) // e) print(ans)