<style>
html, body, .ui-content {
background: #222222;
color: #00BFFF;
}
::-webkit-scrollbar {
width: 10px;
}
::-webkit-scrollbar-track {
background: transparent;
}
::-webkit-scrollbar-thumb {
background: linear-gradient(180deg, #2BE8CF60 0%, #2B83E860 100%);
border-radius: 3px;
}
::-webkit-scrollbar-thumb:hover {
background: linear-gradient(180deg, #2BE8CF95 0%, #2B83E895 100%);
}
/* 設定 code 模板 */
.markdown-body code,
.markdown-body tt {
background-color: #ffffff36;
}
.markdown-body .highlight pre,
.markdown-body pre {
color: #ddd;
background-color: #00000036;
}
.hljs-tag {
color: #ddd;
}
.token.operator {
background-color: transparent;
}

</style>
###### tags: `Algorithm_Lab`

# Dijkstra’s Algorithm 結報
## OJ AC截圖

## Code

#include <bits/stdc++.h>
#define INF 100000
using namespace std;

int dijkstra(int &n, int &m, int &s, int &t, vector<vector<pair<int, int>>> &adj) {
    vector<int> dist(n, INF);
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
    // first for distance; second for node
    dist[s] = 0;
    pq.push(make_pair(0, s));
    unordered_set<int> visited;
    while (!pq.empty()) {  // if there isn't more edge -> break
        pair<int, int> u = pq.top();
        pq.pop();
        visited.insert(u.second);
        for (auto &node : adj[u.second]) {
            int temp = u.first + node.second;
            if (temp < dist[node.first]) {             // relax
                dist[node.first] = temp;               // update distance
                pq.push(make_pair(temp, node.first));  // push smaller distance
            }
        }
        if (visited.size() > n) break;  // if all the node has been visited -> break
    }
    return dist[t];
}
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int _case;
    cin >> _case;
    for (int i = 1; i <= _case; ++i) {
        int n, m, s, t;
        cin >> n >> m >> s >> t;
        vector<vector<pair<int, int>>> adj(n, vector<pair<int, int>>());
        // first for node; second for distance
        for (int i = 0; i < m; ++i) {
            int v1, v2, length;
            cin >> v1 >> v2 >> length;
            adj[v1].push_back(make_pair(v2, length));
            adj[v2].push_back(make_pair(v1, length));
        }
        cout << "Case #" << i << ": ";
        int distance = dijkstra(n, m, s, t, adj);
        if (distance != INF)
            cout << distance << endl;
        else
            cout << "unreachable" << endl;
    }
    return 0;
}

### $n$ is the number of vertex, $m$ is the number of edge
## 空間複雜度分析
* $adj(2 * m),$ $dist(n),$ $pq(m),$ $visited(n)$
* $= 3 * m + 2 * n$
* $O(m + n)$

## 時間複雜度分析

### Best Case && Worst Case
* Make adjlist$(m)$
* for迴圈走訪adj總共$m$次
* while迴圈中($2 *m * \log m$)
* $=2 * m + 2 *m * \log m$
* $O(m\log m)$

## DATE
2023/05/08