C++を勉強中です。
与えられる距離行列はサイズ$N$が非常に大きい場合$N^{2}$で確保してしまうと初期化に時間がかかる。
エッジが存在する場所だけに対して情報を保持する。
そのために以下のようにノードuに対して行き先のノードvとその距離costを保持した構造体を要素にもつベクトルを作成する。
penguinshunya.hatenablog.com
vector<vector<Edge>> G(N)
でエッジの情報管理する。
G[u]
はノードu
と接続するエッジごとに構造体Edge
を保持している。
イメージはこんな感じG[u] = [E1, E2, E3]
。
なので2次元のvectorになっている。