leetcode 743.网络延时时间

思路：迪杰斯特拉最短路径

总结起来其实就两件事：

1.从所给起点开始能不能到达所有点；

2.如果能够到达所有点，那么这个时候需要判断每一个点到源点的最短距离，然后从这些点中求出最大值。

所以用最小路径求解是最划算的选择。

1. 第一步，选源点到哪个节点近且该节点未被访问过
2. 第二步，该最近节点被标记访问过
3. 第三步，更新非访问节点到源点的距离（即更新minDist数组）

这里就是一个模板题，里面有注释，可以细看。

class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<int>>grid(n+1,vector<int>(n+1,INT_MAX));//图vector<bool>st(n+1,false);//每个结点是否被访问到vector<int>minRoad(n+1,INT_MAX);//从源点到i点的最小路径for(int i=0;i<times.size();i++){//构建邻接矩阵int x=times[i][0];int y=times[i][1];int quan=times[i][2];grid[x][y]=quan;}minRoad[k]=0;//源点自身int cur=0;//记录距离源点最近的节点for(int i=1;i<=n;i++){//管理更新次数，因为每一次都有点加进来，距离上会发生变化int mins=INT_MAX;//每次都是最大值，不能放外面。for(int v=1;v<=n;v++){//找最近节点，记录节点数if(!st[v]&&minRoad[v]<=mins){mins=minRoad[v];cur=v;}}st[cur]=1;//遍历到最近节点for(int v=1;v<=n;v++){//更新最小路径值if(!st[v]&&grid[cur][v]!=INT_MAX&&minRoad[cur]+grid[cur][v]<minRoad[v]){minRoad[v]=minRoad[cur]+grid[cur][v];}}}int res=0;for(int i=1;i<=n;i++){if(minRoad[i]==INT_MAX)return -1;else{res=max(res,minRoad[i]);}}return res;}
};