vectorのi番目の要素は配列になってるの？

Question

###ダイクストラ法を勉強中です
辺に重み(非負)があるときの最短経路を解く方法としてダイクストラ法があります。
BFSとはqueueの扱い以外にそこまで違いがないので理解しやすいです。

しかし、今まで無意識だった辺のつなぎかたに疑問を持ちました。

以下参考にしてるダイクストラのコード

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

#define INF 1e+9
#define MAX_V 10

struct edge {
    int to;
    int cost;
};

// <最短距離, 頂点の番号>
using P = pair<int, int>;

int V;
vector<edge> G[MAX_V];
int d[MAX_V];

void dijkstra(int s) {
    priority_queue<P, vector<P>, greater<P> > que;
    fill(d, d+V, INF);
    d[s] = 0;
    que.push(P(0, s));

    while (!que.empty()) {
        P p = que.top();
        que.pop();
        int v = p.second;
        if (d[v] < p.first) continue;

        for (int i=0; i<G[v].size(); ++i) {
            edge e = G[v][i];
            if (d[e.to] > d[v] + e.cost) {
                d[e.to] = d[v] + e.cost;
                que.push(P(d[e.to], e.to));
            }
        }
    }
}

int main() {
    cin >> V;
    int E;
    cin >> E;
    for (int i=0; i<E; ++i) {
        int a, b, c;
        cin >> a >> b >> c;
        edge e = {b, c};
        G[a].push_back(e);
    }
    dijkstra(0);
    for (int i=0; i<V; ++i) {
        if(d[i] != INF)
            cout << "0から" << i << "までのコスト: " << d[i] << endl;
    }
}

###G[i].push_back
G[]は型がedge型の一次元vectorです。
main関数内ではa,b,cがそれぞれ始点、終点、辺のコストで入力されているので、G[a].push_back(e)は今回は有向グラフで点aからつながる点を集めてるようなイメージだとわかりました。

ここで疑問に思ったのは、Gは１次元vectorでG={edge0,edge1,edge2....}となっているはずです。
ここで、G[i].push_backをするとG[i]はedge型の要素なのでedgeiに新しいedgeを入れることになり訳が分からなくなりました。
調べてみても、G.push_backでvectorの一番後ろに要素を追加する方法は出てきますがG[i].push_backjは出てきませんでした。

###試したこと
下のコードを追加してG[i]の要素の数を確かめてみました。

for(int i=0;i<V;i++){
    cout << G[i].size() << endl;
  }

入力:
6 7 //点の数6,辺の数7
0 1 1 //点0→1 コスト1
0 2 3
1 2 4
1 3 2
2 3 3
3 4 1
3 5 1

出力:
2
2
1
2
0
0

確かにGのi番目の要素にedgeが配列のように入っています。

##vectorは一次元でもi番目の要素は宣言した型の配列になっているのか？

今のところi番目の要素に値を追加できてるようなので一次元vectorは２次元配列のようになっていると解釈しています。
G={edge0.edge1,edge2....}ではなく G={0{edge0..},1{edge1..},2{edge2...},.....}
この考え方で合っているのでしょうか？
詳しい方教えていただけると助かります。

Answer 1

vectorのi番目の要素は配列になってるの？

逆ですね。配列の各要素がvector<edge>です。

vector<edge> G[MAX_V]; ですから。

Answer 2

２次元配列のようになっていると解釈しています。

以下が2次元配列っぽいか？という話であれば、正しいと思います。

vector<edge> G[MAX_V];

静的配列と動的配列の表記が混ざっているので分かりにくいですが、（乱暴に説明すると）これは以下のようなものです

vector<vector<edge>> G;
int main() {
  G.resize(MAX_V);
}

i番目の頂点を始点として繋がっている、有向辺の構造体は G[i][0], G[i][1], G[i][2], ... です。

Comments

[kyokio]

ありがとうございます。
vector<edge> G{MAX_V]をvector<edge> G(MAX_V)と勘違いしてました。
要素にvectorを持つ配列なんですね。
ありがとうございました。