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

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

#### input

第一行有兩正整數 $n,m$
$n$ 為點的數量， $m$ 為邊的數量
接下來有 $m$ 行，每行有三整數 $a_i,b_i,w_i$
$\forall a_i,b_i\in\mathbb{N}$ , $-10^9\leq w_i\leq 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
}