AtCoder Beginner Contest 204 のE問題で以下のコードを提出するとWAになってしまいます。
サンプルコードはすべてACで、全体では23/36がACになるのに、なぜ一部でWAになるのかわかりません。
原因がわかる方是非教えていただきたいです。
import heapq
from sys import stdin
def calc_best_time(C, D):
func = lambda x: x + C + D // (x+1)
lower = int(pow(D, 0.5)-1)
upper = lower + 1
if lower < 0: return 0, func(0), func
if func(lower) < func(upper): return lower, func(lower), func
else: return upper, func(upper), func
def dijkstra(root, adjacencies):
min_time = {vertex: -1 for vertex in adjacencies}
heap = [(0, root)]
searched = set()
while heap:
time, vertex = heapq.heappop(heap)
if vertex in searched: continue
searched.add(vertex)
min_time[vertex] = time
for adj_vertex, (start, end, func) in adjacencies[vertex].items():
if adj_vertex in searched: continue
if time <= start: heapq.heappush(heap, (end, adj_vertex))
else: heapq.heappush(heap, (func(time), adj_vertex))
return min_time
def main():
input = lambda: stdin.readline().rstrip()
N, M = map(int, input().split())
adjacencies = {vertex: {} for vertex in range(1, N+1)}
for _ in range(M):
A, B, C, D = map(int, input().split())
adjacencies[A][B] = calc_best_time(C, D)
adjacencies[B][A] = calc_best_time(C, D)
min_time = dijkstra(1, adjacencies)
print(min_time[N])
if __name__ == '__main__':
main()