C. Dijkstra?, Easy
- no tricks just plain implementation.
- implemented the most basic dijsktra
- implementation method was using priority queue
Headers
```cpp
#define vll vector
using ll = long long int;
vector<vector> adj = vector<vector>(n + 1);
for (int i = 0; i < m; i++) {
ll a, b, w;
cin >> a >> b >> w;
adj[a].push_back({b, w});
adj[b].push_back({a, w});
}
int s = 1; /* source */
vll dist(n + 1, INF);
vll path(n + 1, INF);
dist[s] = 0;
```
</details>
Implementation stuff
```cpp
priority_queue<pll, vector, greater> pq;
pq.push({0, s});
/* Format is (distance, vertex) */
while (!pq.empty()) {
auto front = pq.top();
pq.pop();
ll d = front.first;
ll u = front.second;
if (d > dist[u])
continue; // trying to understand this
for (const auto &v : adj[u]) {
/*
* take v.first as 'to'
* u as 'from'
*/
if (dist[u] + v.second < dist[v.first]) {
dist[v.first] = dist[u] + v.second;
pq.push({dist[v.first], v.first});
path[v.first] = u;
}
}
}
```
</details>
Tracking Shortest distance
```cpp
vll ans;
for (int i = n; i != 1; i = path[i])
ans.push_back(i);
ans.push_back(1);
reverse(all(ans));
```