743. 网络延迟时间
有 n 个网络节点，标记为 1 到 n。
给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。
现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。
示例 1：
输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2
题源：（点击题目）
题解：
最短路径，开始做成了bfs的遍历，因为路径上是有权重的，所以应该是最短路径（dijkstra，SPFA, Floyed……），我采用的是SPFA
注意点，对于结果，不能在做的过程中得道，因为距离数组dis[]还会不停更新。
代码1： SPFA没有用vis数组优化
class Solution { public: int networkDelayTime(vector<vector<int>>& times, int n, int k) { map<int , vector<pair<int,int>> > mp; queue<int> Q; for(auto i: times) mp[i[0]].push_back(make_pair(i[1],i[2])); int dis[105]; memset(dis,-1,sizeof(dis)); dis[k]=0; Q.push(k); int maxti=0; while(!Q.empty()) { int p=Q.front(); Q.pop(); for(auto i:mp[p]) { if(dis[i.first]>=0 && i.second+dis[p]>=dis[i.first]) continue; dis[i.first]=i.second+dis[p]; Q.push(i.first); // maxti=max(maxti,dis[i.first]); //不能在这个位置比较，因为此时dis[]并不是最短的时间 } } for(int i=1;i<=n;i++) if (dis[i]<0) return -1; else maxti=max(maxti,dis[i]); // 需要在这个位置进行比较 return maxti; } };
代码2：SPFA方法
class Solution { public: int networkDelayTime(vector<vector<int>>& times, int n, int k) { map<int , vector<pair<int,int>> > mp; queue<int> Q; for(auto i: times) mp[i[0]].push_back(make_pair(i[1],i[2])); // 构建一个自己的图 int dis[105]; memset(dis,-1,sizeof(dis)); // 表示该节点是否被访问过，并存被访问最短时间 bool vis[105]; memset(vis,0,sizeof(vis)); // 表示是否在Q队列中 dis[k]=0; vis[k]=1; Q.push(k); int maxti=0; while(!Q.empty()) { int p=Q.front(); Q.pop(); vis[p]=0; for(auto i:mp[p]) { if(dis[i.first]>=0 && i.second+dis[p]>=dis[i.first]) continue; dis[i.first]=i.second+dis[p]; // 不在队列或队列中，都要被更新 if (!vis[i.first]) // 如果不在队列中，放入队列 { Q.push(i.first); vis[i.first]=1; } } } for(int i=1;i<=n;i++) if (dis[i]<0) return -1; else maxti=max(maxti,dis[i]); return maxti; } };