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

总结起来其实就两件事：

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;
    }
};