(重み付き)グラフを扱います。
weighted_graph wg(ll n);n頂点0辺のグラフを構築します。
\(O(n)\)
wg.add_edge(ll a,ll b,ll cost = 1);
wg.add_directed_edge(ll from,ll to,ll cost = 1);
頂点\(a\)と\(b\)を結ぶ重み\(cost\)の無効辺または、
頂点\(from\)から\(to\)への重み\(cost\)の有効辺を貼ります。
costを指定しなかった場合重み1として扱います。
\(O(1)\)
wg.dijkstra(ll s);dijkstra法を用いて頂点\(s\)から各頂点への最短距離を求めます。
vector<ll> res
\(res_i\)は頂点\(s\)から\(i\)への最短距離。
\(O(n)\)
for(auto edge : wg.e[i]){
ll to,cost;
tie(to,cost) = edge;
}\(e_i\)は頂点\(i\)から移動することのできる "頂点番号と、その頂点へ向かう辺のコスト"のpairです。