上次沒講到一些圖的基本知識，補充一下

假設今天題目的輸入格式如下

input

第一行有兩正整數

$n,m$

$n$ 為點的數量，

$m$ 為邊的數量
接下來有

$m$ 行，每行有三整數

$a_i,b_i,w_i$

$\mathrm{\forall }{a}_i,b_i\in \mathbb{N}$ ,

$-{10}^9\le w_i\le {10}^9$

通常會有以下兩種儲存方式

---

Adjacency Matrix / 鄰接矩陣

因為這種儲存方式和邊的數量較無關，因此在稠密圖表現較佳
如果兩點之間有多條邊，且有權重的話比較麻煩
比較少用，但還是會用到

cin >> n >> m;
vector<vector<int>> e(n, vector<int>(n));
for(int i = 0; i != m; i++){
    int a, b, w;
    cin >> a >> b >> w, a--, b--;
    e[a][b] = e[b][a] /*undirected_graph*/ = w;
}

---

Adjacency List / 鄰接串列

因為這種儲存方式和邊的數量有關，因此在稀疏圖的表現會比較好
一般解題都使用這種儲存方式

struct edge{
    int b, w;
    edge(int x, int y): b(x), w(y) {}
};
cin >> n >> m;
vector<vector<edge>> e(n);
for(int i = 0; i != m; i++){
    int a, b, w;
    cin >> a >> b >> w, a--, b--;
    e[a].emplace_back(b, w);
    e[b].emplace_back(a, w); //undirected_graph
}