グリッドをグラフに変換する
コンストラクタ
- GT_GridGraph(ysize, xsize, exsize = 0): (ysize, xsize) のグリッドをグラフに変換（exsizeは超頂点の数）
- Vertex(y, x): グリッド座標 (y, x) に対応する頂点インデックスを返す
- ExVertex(ll ex): 超頂点の頂点インデックスを返す（引数は0-indexで指定）
- AddDirectedEdge(g, vnow, vnext, cost): 頂点指定で有向グラフを張る（特に超頂点を使うときに便利）
- AddDirectedEdge(g, ynow, xnow, ynext, xnext, cost): グリッド座標指定で有向グラフを張る
- AddUndirectedEdge(g, vnow, vnext, cost): 頂点指定で無向グラフを張る（特に超頂点を使うときに便利）
- AddUndirectedEdge(g, ynow, xnow, ynext, xnext, cost): グリッド座標指定で無向グラフを張る
#include <bits/stdc++.h> namespace NyaaLIB { struct GT_GridGraph { using ll = long long; using wgraph = std::vector<std::vector<std::pair<ll, ll>>>; ll ysize, xsize, exsize; GT_GridGraph(ll ysize, ll xsize, ll exsize = 0) : ysize(ysize), xsize(xsize), exsize(exsize) {} ll Vertex(ll y, ll x) { return y * xsize + x; } ll ExVertex(ll ex) { return ysize * xsize + ex; } void AddDirectedEdge(wgraph& g, ll vnow, ll vnext, ll cost) { g[vnow].push_back({ vnext, cost }); } void AddDirectedEdge(wgraph& g, ll ynow, ll xnow, ll ynext, ll xnext, ll cost) { g[Vertex(ynow, xnow)].push_back({ Vertex(ynext, xnext), cost }); } void AddUndirectedEdge(wgraph& g, ll vnow, ll vnext, ll cost) { g[vnow].push_back({ vnext, cost }), g[vnext].push_back({ vnow, cost }); } void AddUndirectedEdge(wgraph& g, ll ynow, ll xnow, ll ynext, ll xnext, ll cost) { g[Vertex(ynow, xnow)].push_back({ Vertex(ynext, xnext), cost }), g[Vertex(ynext, xnext)].push_back({ Vertex(ynow, xnow), cost }); } }; }
