目的 負辺のないグラフで単一始点全点間最短路を求めるアルゴリズム. 各地点でもっとも近い頂点から距離が確定していく. 距離順でソートされたヒープを用いると, 効率よく距離を確定していくことができる. オーダー O(ElogV) 条件 dijkstra(g, s): 重み付き…

説明 グラフを扱う際のテンプレート。 コード template <typename T = int> struct Edge { int from, to; T cost; int idx; Edge() = default; Edge(int from, int to, T cost = 1, int idx = -1) : from(from), to(to), cost(cost), idx(idx) {} operator int() const { retur</typename>…

目的 二次元格子状領域において、幅優先探索を行う。 また、要素xと要素yそれぞれが属するグループを併合することが可能。 オーダー O(HW) 条件 grid_bfs(s, start, wall):= グリッド s 上にある文字 start からすべてのマスへの最短距離を求める。wall には…