难度 中等

题目 Leetcode:

You are given a network of n nodes, labeled from 1 to n. You are also given times, a list of travel times as directed edges times[i] = (ui, vi, wi), where ui is the source node, vi is the target node, and wi is the time it takes for a signal to travel from source to target.

We will send a signal from a given node k. Return the time it takes for all the n nodes to receive the signal. If it is impossible for all the n nodes to receive the signal, return -1.

题目解析

这题和Codeforces上的一题形式很类似，Dijkstra。

但还是先说这题的思路，如何能找到最短的路径，最直接的就是找到离初始点最近的那个点，然后再找离这个点最近的点。然后我们再根据题意，从 k 节点出发，到达x节点的时间就是k 节点到x节点的最短路的长度。因此我们需要求出节点 k 到其余所有点的最短路，其中的最大值就是答案。若存在从 k 出发无法到达的点，则返回 -1。

解析完毕，以下是参考代码

 1 class Solution {
 2 public:
 3     int networkDelayTime(vector<vector<int>>& times, int n, int k) {
 4         int ans;
 5         //n个节点 从k节点开始 
 6         //最短路径
 7         vector<vector<int>>mp(n+1,vector<int>(n+1,10005));
 8         for(int i=1;i<=n;i++)mp[i][i]=0;
 9         for(const auto &t:times)mp[t[0]][t[1]]=t[2];
10         for(int poin=1;poin<=n;poin++)
11         {
12             for(int i=1;i<=n;i++)//遍历矩阵
13             {
14                 for(int j=1;j<=n;j++)
15                 {
16                     if(mp[i][j]>mp[i][poin]+mp[poin][j])
17                     mp[i][j]=mp[i][poin]+mp[poin][j];
18                 }
19             }
20         }
21         ans=*max_element(mp[k].begin()+1,mp[k].end());
22         return ans==10005?-1:ans;
23     }
24 };