0

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()

1 件の回答 1

1

多重辺が考慮されてません
入力例2のように同じ頂点を結ぶ辺が複数あった場合に最後のものしか使えないようになっています。

この質問に回答するには、ログインする必要があります。

求めていた回答ではありませんか? のタグが付いた他の質問を参照する。