[AtCoder] [經典競程 90 題] 013 - Passing（★5）

題目連結: https://atcoder.jp/contests/typical90/tasks/typical90_m 題目大意:
給一個 $N$ 個點 $M$ 條邊的圖，對於所有點 $u$ 求問強迫經過點 $u$ 時 $1$ 走到 $n$ 的最短路是多長。

---

從 $1$ 跟 $N$ 分別做一次 Dijkstra 就好了。

#include <bits/stdc++.h>
using namespace std;
using lld = int64_t;
const lld INF = static_cast<lld>(1) << 60;


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	int n, m; cin >> n >> m;
	vector<vector<pair<int, lld>>> g(n);
	for (int i = 0; i < m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		g[--u].emplace_back(--v, w);
		g[v].emplace_back(u, w);
	}
	auto shortest_path = [&g] (int s, vector<lld> &d) {
		vector<bool> vis(d.size());
		fill(d.begin(), d.end(), INF);
		priority_queue<pair<lld,int>> pq;
		d[s] = 0;
		pq.emplace(-d[s], s);
		while (not pq.empty()) {
			int u = pq.top().second;
			pq.pop();
			if (vis[u]) continue;
			vis[u] = true;
			for (auto [v, w]: g[u]) {
				if (d[u] + w < d[v]) {
					d[v] = d[u] + w;
					pq.emplace(-d[v], v);
				}
			}
		}
	};
	vector<lld> d1(n), dn(n);
	shortest_path(0, d1);
	shortest_path(n - 1, dn);
	for (int i = 0; i < n; ++i) {
		cout << d1[i] + dn[i]<< '\n';
	}
	return 0;
}