77604


AtCoder Beginner Contest 204 のE問題で以下のコードを提出するとWAになってしまいます。  
サンプルコードはすべてACで、全体では23/36がACになるのに、なぜ一部でWAになるのかわかりません。  
原因がわかる方是非教えていただきたいです。

[code]

    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()
    
[/code]


CC BY-SA 4.0
2021-06-16T02:10:05.703
77589
2021-06-16T16:14:59.330
41730
question
python python3
AtCoder Beginner Contest 204 E問題でWAになる


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


CC BY-SA 4.0
2021-06-16T16:14:59.330
77604
2021-06-16T16:14:59.330
33033
77589
answer