做微信扫码网站,c做项目的网站,好视通会议软件收费价格,做网站每月收入思路#xff1a;迪杰斯特拉最短路径
总结起来其实就两件事#xff1a;
1.从所给起点开始能不能到达所有点#xff1b;
2.如果能够到达所有点#xff0c;那么这个时候需要判断每一个点到源点的最短距离#xff0c;然后从这些点中求出最大值。
所以用最小路径求解是最划…思路迪杰斯特拉最短路径
总结起来其实就两件事
1.从所给起点开始能不能到达所有点
2.如果能够到达所有点那么这个时候需要判断每一个点到源点的最短距离然后从这些点中求出最大值。
所以用最小路径求解是最划算的选择。
第一步选源点到哪个节点近且该节点未被访问过第二步该最近节点被标记访问过第三步更新非访问节点到源点的距离即更新minDist数组
这里就是一个模板题里面有注释可以细看。
class Solution {
public:int networkDelayTime(vectorvectorint times, int n, int k) {vectorvectorintgrid(n1,vectorint(n1,INT_MAX));//图vectorboolst(n1,false);//每个结点是否被访问到vectorintminRoad(n1,INT_MAX);//从源点到i点的最小路径for(int i0;itimes.size();i){//构建邻接矩阵int xtimes[i][0];int ytimes[i][1];int quantimes[i][2];grid[x][y]quan;}minRoad[k]0;//源点自身int cur0;//记录距离源点最近的节点for(int i1;in;i){//管理更新次数因为每一次都有点加进来距离上会发生变化int minsINT_MAX;//每次都是最大值不能放外面。for(int v1;vn;v){//找最近节点记录节点数if(!st[v]minRoad[v]mins){minsminRoad[v];curv;}}st[cur]1;//遍历到最近节点for(int v1;vn;v){//更新最小路径值if(!st[v]grid[cur][v]!INT_MAXminRoad[cur]grid[cur][v]minRoad[v]){minRoad[v]minRoad[cur]grid[cur][v];}}}int res0;for(int i1;in;i){if(minRoad[i]INT_MAX)return -1;else{resmax(res,minRoad[i]);}}return res;}
};
