ABC192 E Train ~Dijkstraの実装でハマった話~ - Qiita

はじめに 本記事は競技プログラミングにおいて解くのに困った問題について、なぜその解法に思い至るのか、どのような所でハマったか等のポイントをメモした、筆者の筆者による筆者のための備忘録となっております。読まれることを意識していないので文章がとっ散らかってます。 問題 問題はこちら。 概略 $N$個の頂点と$M$本の辺からなる無向グラフがある。辺$i$は頂点$A_i, B_i$を結んでおり、この間の移動には$T_i$の時間を要する。ただし時刻が$K_i$の倍数である時のみこの辺の移動を開始できる。 頂点$X$を時刻0に出発して頂点$Y$に到達するまでの最短時間を求めよ。 提出解答 提出解答はこちら。 from heapq import heappush, heappop, heapify n, m, x, y = map(int, input().split()) path = [[] for