1. 題目來源

鏈接：743. 網(wǎng)絡延遲時間

相關鏈接：

• [圖+最短路+模板] 五大最短路常用模板)

2. 題目解析

怎么講呢，挺抽象的…很久沒寫最短路算法了。反正也是寫出來了，但脫離了模板，把自己還給繞進去了…

這塊還是按照模板來寫吧。

至于具體的算法思想，看相關鏈接即可。

---

• 時間復雜度：$O(nm)$
• 空間復雜度：$O(1)$

---

標準 spfa

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<pair<int, int>> g[n + 1];for (auto& e : times) {int x = e[0], y = e[1], w = e[2];g[x].push_back({y, w});}// 標準 spfa 算法queue<int> q; vector<int> dist(n + 1, 1e9);   // 注意這里初始化的是最大值vector<bool> st(n + 1, false);q.push(k);dist[k] = 0;while (q.size()) {auto x = q.front(); q.pop();st[x] = false; // x 不在隊列中for (auto& [y, w] : g[x]) { // 更新 x 點臨邊if (dist[y] > dist[x] + w) { // 如果 y 點可以被 x 點更新dist[y] = dist[x] + w; // 則更新if (!st[y]) { // 如果 y 不在隊列中，則加入q.push(y);st[y] = true;}}}}int res = -1e9;for (int i = 1; i <= n; i ++ ) {if (dist[i] == 1e9) return -1;  // 這里也是拿最大值進行的判斷res = max(res, dist[i]);}return res;}
};

以下是 y 總寫的 spfa 模板，大同小異。

const int N = 110, M = 6010, INF = 0x3f3f3f3f;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];class Solution {
public:void add(int a, int b, int c) {e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;}void spfa(int start) {queue<int> q;q.push(start);memset(dist, 0x3f, sizeof dist);dist[start] = 0;while (q.size()) {int t = q.front();q.pop();st[t] = false;for (int i = h[t]; ~i; i = ne[i]) {int j = e[i];if (dist[j] > dist[t] + w[i]) {dist[j] = dist[t] + w[i];if (!st[j]) {q.push(j);st[j] = true;}}}}}int networkDelayTime(vector<vector<int>>& times, int n, int k) {memset(h, -1, sizeof h);idx = 0;for (auto& e: times) {int a = e[0], b = e[1], c = e[2];add(a, b, c);}spfa(k);int res = 1;for (int i = 1; i <= n; i ++ ) res = max(res, dist[i]);if (res == INF) res = -1;return res;}
};作者：yxc
鏈接：https://www.acwing.com/activity/content/code/content/1011633/
來源：AcWing
著作權歸作者所有。商業(yè)轉載請聯(lián)系作者獲得授權，非商業(yè)轉載請注明出處。

---

2024年11月26日00:08:57
這里不知道隨便寫的 spfa 也過了…
不要留下壞印象…

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<pair<int, int>>> g(n, vector<pair<int, int>>{});for (auto& e : times) {int x = e[0] - 1, y = e[1] - 1, w = e[2];g[x].push_back({y, w});}queue<int> q; vector<int> st(n, -1);  // 即是 st 又是 dist，用 -1 做狀態(tài)標記位k = k - 1;q.push(k);st[k] = 0;while (q.size()) {auto x = q.front(); q.pop();for (auto& [y, w] : g[x]) {if (st[y] == -1 || st[y] > st[x] + w) { // 這里其實參考的是 dij 算法，又像 spfast[y] = st[x] + w;q.push(y);}}}int res = -1e9;for (int& x : st) {if (x == -1) return -1;res = max(res, x);}return res;}
};