解法1：頂点を倍にする 考え方 回答例 解法1：頂点を倍にする考え方フェネック「いま車に乗ってるのか電車に乗ってるのかで頂点を倍にして、1つのグラフで1回だけダイクストラをする解法もあるよ。ちょっと違うけどこういうイメージだねー」https://t.co/9au…

考え方 回答例 考え方ある頂点から他の頂点への最短経路を求めると，最短経路からなる集合は木になる（最短経路木）． よって，最短経路で通る辺を列挙すれば良い．回答例 import heapq N, M = map(int, input().split()) G = [[] for _ in range(N)] E = {}…

単一始点 BFS ダイクストラ法 01BFS 単一始点ある頂点からの最短距離を求めたい場合．負の辺がないとする．未確定頂点のうち，最短距離のものは確定できる（他の頂点からの更新で小さくなりえない）．つまり，最短距離の未確定頂点の集合を取り出せるデータ…

「スコアの符号を変えればダイクストラが使える！」と思って嘘解法で通してしまいました．．．負の辺を含まない形に問題を修正しなければなりません． Editorial - AtCoder Beginner Contest 237 考え方 符号の反転 ポテンシャルの導入 解くべき問題 回答例 …