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

考え方 回答例 考え方隣接頂点との距離が1なので，BFSで最短距離を求められる． 最短経路問題 - 競プロはじめました各$p_{i}$からの各頂点の最短距離$d$を求めて，$d 各$i$について$p_{i}$からの最短距離が$d_{i}$に等しい頂点の集合をbとする．bがwhiteに包…

考え方 回答例 考え方原点から$\sqrt{M}$の距離にある点を求めておけば，任意の点についても原点をずらすだけで$\sqrt{M}$の距離にある点が求まる．半径$r$の円周上の格子点の個数は$2\pi r$以下なので，高々$O(N)$個．よって，全ての点を1回ずつみながら遷…

考え方 回答例 考え方全点対最短経路問題（すべての2頂点間の最短路を求める問題）が解けていれば， ある2頂点を結ぶ辺は， その2頂点を迂回する（複数の辺を使う）ことで，同じコスト「以下」で到達できるならなくてもよい（※1） ことからこの問題も解ける…

考え方 回答例 考え方制約から 距離0：1コ 距離1：1×3コ 距離2：1×3×3コ 距離3：1×3×3×3コ で，各クエリに対して40コ調べれば良いから，言われたとおり計算するだけでよい．回答例訪れた頂点の管理をするために全頂点の配列を用意するとTLEする（各頂点への…

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

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

ABC246E - Bishop 2 - 競プロはじめましたの類題． 考え方 回答例 考え方最短経路問題 - 競プロはじめました コストゼロで行けるものを優先してみればBFSで解ける． キューからpopしたものから更新される頂点はコスト＋1される．コストゼロで到達できる頂点…

【参考】最短経路問題 - 競プロはじめました 方法1 考え方 回答例 方法2 考え方 回答例 参考 方法1考え方ダイクストラ法と同じように，最短距離が未確定の頂点のうち，最小のものから確定させて更新すれば良さそう．1マスずつ動かす問題に帰着するにはどうす…

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

考え方 回答例 考え方 「重みなし」グラフの最短経路を求める問題になる→BFS 桁が減る操作はないので，10 ** 6を超えたら打ち切ることができる 回答例 from collections import deque a, N = map(int, input().split()) q = deque() q.append(1) dist = [-1]…