有 N 个网络节点，标记为 1 到 N。
给定一个列表 times，表示信号经过有向边的传递时间。 times[i] = (u, v, w)，其中 u 是源节点，v 是目标节点， w 是一个信号从源节点传递到目标节点的时间。
现在，我们从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1。
示例：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], N = 4, K = 2
输出：2
注意:
N 的范围在 [1, 100] 之间。
K 的范围在 [1, N] 之间。
times 的长度在 [1, 6000] 之间。
所有的边 times[i] = (u, v, w) 都有 1 <= u, v <= N 且 0 <= w <= 100。
来源：力扣（LeetCode）
链接：https://leetcode-cn.com/problems/network-delay-time
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
1 //使用优先队列完成迪杰斯特拉算法 2 //图的存储用邻接表 3 class Solution { 4 public: 5 map<int, vector<pair<int,int>>> Map; 6 int inf = 101; 7 int root;//源节点 8 vector<int> v;//存储已找到最短路径的结点 9 vector<int> dis;//存储最短路径 10 struct Cell 11 { 12 int node; 13 int distance; 14 Cell(int _node, int _val) :node(_node),distance(_val){}; 15 bool operator <(const Cell& c)const//优先队列默认是大顶堆 16 { 17 return distance > c.distance; 18 } 19 }; 20 void dijkstra() 21 { 22 priority_queue<Cell> pq; 23 pq.push({ root,0 }); 24 while (!pq.empty()) 25 { 26 Cell c = pq.top(); 27 pq.pop(); 28 if (v[c.node])continue; 29 v[c.node] = 1; 30 dis[c.node] = c.distance; 31 for (auto item : Map[c.node])//这里是松弛 32 if (item.second + c.distance < dis[item.first]) 33 pq.push({ item.first,item.second + c.distance }); 34 } 35 } 36 int networkDelayTime(vector<vector<int>>& times, int N, int K) { 37 root = K; 38 dis.resize(N + 1, inf); 39 v.resize(N + 1, 0); 40 for (auto item : times) 41 Map[item[0]].push_back({ item[1],item[2] });//初始化邻接表 42 dijkstra(); 43 int res = *max_element(dis.begin() + 1, dis.end()); 44 return res == inf ? -1 : res; 45 } 46 };
1 //常规迪杰斯特拉 不知道为啥速度更快一些 2 //图的存储用邻接矩阵 3 class Solution { 4 public: 5 int inf = 101; 6 vector<vector<int>> Map;//图 7 int n; 8 int root;//源节点 9 vector<int> v;//存储已找到最短路径的结点 10 vector<int> dis;//存储最短路径 11 void dijkstra() 12 { 13 v[root] = 1; 14 dis[root] = 0; 15 for (int i = 1; i <= n; i++) 16 { 17 int k = 0; 18 for (int j = 1; j <= n; j++)//找出距离最近的点 19 if (!v[j] && (k == 0 || dis[j] < dis[k])) 20 k = j; 21 v[k] = 1;//加入集合 22 for (int j = 1; j <= n; ++j)//松弛 23 if (!v[j] && dis[k] + Map[k][j] < dis[j]) 24 dis[j] = dis[k] + Map[k][j]; 25 } 26 } 27 int networkDelayTime(vector<vector<int>>& times, int N, int K) { 28 Map.resize(N + 1, vector<int>(N + 1, inf)); 29 root = K; 30 n = N; 31 dis.resize(N + 1, inf); 32 v.resize(N + 1, 0); 33 for (auto item : times) 34 { 35 if (item[0] == K)dis[item[1]] = item[2]; 36 Map[item[0]][item[1]] = item[2]; 37 } 38 dijkstra(); 39 int res = *max_element(dis.begin() + 1, dis.end()); 40 return res == inf ? -1 : res; 41 } 42 };
参考 https://www.zhihu.com/question/20630094/answer/758191548
原文：https://www.cnblogs.com/lancelee98/p/13394754.html