《灵珠觉醒：从零到算法金仙的C++修炼》卷三·天劫试炼（49）万鸦壶焚网络 - 网络延迟时间（Bellman-Ford）

哪吒在数据修仙界中继续他的修炼之旅。这一次，他来到了一片神秘的万鸦壶网络，壶中网络错综复杂，节点之间的延迟各不相同。壶的入口处有一块巨大的石碑，上面刻着一行文字：“欲破此壶，需以万鸦壶之力，焚网络，网络延迟显真身。”

哪吒定睛一看，石碑上还有一行小字：“网络拓扑结构如下，节点K到其他所有节点的最短延迟时间的最大值即为网络延迟时间。”哪吒心中一动，他知道这是一道关于网络延迟时间的难题，需要通过Bellman-Ford算法来计算从起点到所有节点的最短路径，进而找到最大延迟时间。

暴力解法：万鸦壶的初次尝试

哪吒心想：“要计算网络延迟时间，我可以尝试所有可能的路径。”他催动万鸦壶之力，从起点节点开始，逐个节点访问，记录每条路径的延迟时间，试图找到最短路径。

#include <vector>
#include <climits>
using namespace std;int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<int> dist(n + 1, INT_MAX);dist[k] = 0;for (int i = 0; i < n - 1; ++i) {for (auto& time : times) {int u = time[0];int v = time[1];int w = time[2];if (dist[u] != INT_MAX && dist[u] + w < dist[v]) {dist[v] = dist[u] + w;}}}int maxDelay = 0;for (int i = 1; i <= n; ++i) {if (dist[i] == INT_MAX) return -1;maxDelay = max(maxDelay, dist[i]);}return maxDelay;
}

哪吒成功地计算了网络延迟时间，但万鸦壶的光芒却黯淡了下来。他意识到，这种方法虽然可行，但效率低下，尤其是当网络节点数量很多时，灵力消耗巨大。

C++语法点

在C++中，Bellman-Ford算法涉及到图的邻接表表示和距离数组的更新。以下是一些重要特性：

• 邻接表：

  • 使用vector<vector<int>>表示图的邻接表。
  • 常用操作：
    • times：存储所有边的信息，每条边包含起点、终点和权重。

• 距离数组