# 最短路徑
:::info
有向無向皆可
:::

dijkstra
---
* 邊的權重不能為負
* 有n個點，設s為起點，$dis[v]$代表s到v的最點距離，$weight[a][b]$為a到b的權重，$done[v]=1$代表點v已走過, $parent[v]$是v的上一個點
* $dis[s]=0$，其餘為無限大
* done皆為0
* **步驟：**
1. 從沒走過的點中，找一個點x其$dis[x]$最小的，設done[x]=1，所以一開始x就是起點s
* 用priority_queue找dis[x]最小的，每次找最小又還沒走過的點，所以每次push{dis[u], u}，pop要檢查done[x]是否為1
2. 對於每個x連到的點y，做$dis[y]=min(dis[y], dis[x]+weight[x][y])$
3. 重複 1.
* $O(V+ElogV)$

#define EB emplace_back
#define PII pair<int,int>
#define F first
#define S second
#define NL "\n"

using namespace std;

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    int n, m, u, v, w;
    cin>>n>>m;
    vector<vector<PII>> gh(n, vector<PII>());
    rep(0,m){
        cin>>u>>v>>w;
        gh[u].EB(make_pair(v, w));
        gh[v].EB(make_pair(u, w));
    //doesn't matter if there's multiple line between two nodes, the algorithm will take the least one
    }

    //init
    vector<int> done(n, 0);
    vector<int> parent(n);
    vector<int> dis(n, INT_MAX);
    dis[0]=0; //default dis[s] is 0
    
    priority_queue<PII, vector<PII>, greater<PII>> pq;
    pq.push({dis[0], 0});
    
    while(!pq.empty()){
        PII x=pq.top();
        pq.pop();
        if(done[x.S]) continue;
        done[x.S]=1;
        for(auto a:gh[x.S]){
            if(done[a.F]) continue; //not necessary
            if(dis[x.S]+a.S<dis[a.F]){
                dis[a.F]=dis[x.S]+a.S;
                parent[a.F]=x.S;
                pq.push({dis[a.F], a.F});
            }
        }
    }
}

bellman ford
---

floyd warshall
---
* 動態規劃：對於dis[i][j]，枚舉i~j的中點k
* 可用於權重為負值的情況，但不能有負環（可偵測負環）
* **找出所有點對的距離**

for(int k = 1; k <= n; k++){
  for(int i = 1; i <= n; i++){
    for(int j = 1; j <= n; j++){
    	dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]);
    }
  }
}