广告机 东莞网站建设,国家企业信用公示系统官网(全国),4d网站广告图用什么做的,如何跟进psd做网站题目来源#xff1a; leetcode题目#xff0c;网址#xff1a;1334. 阈值距离内邻居最少的城市 - 力扣#xff08;LeetCode#xff09;
解题思路#xff1a; 利用贝尔曼-福德算法计算出每个节点到其余节点的最短距离后对符合条件的计数#xff0c;返回计数最小且编…题目来源 leetcode题目网址1334. 阈值距离内邻居最少的城市 - 力扣LeetCode
解题思路 利用贝尔曼-福德算法计算出每个节点到其余节点的最短距离后对符合条件的计数返回计数最小且编号最大的城市。
解题代码
class Solution {
public:int findTheCity(int n, vectorvectorint edges, int distanceThreshold) {vectorvectorint matrixgetMatrix(n,edges); //距离向量int res0; //城市编号int min10001; //符合要求的其他城市数目for(int i0;imatrix.size();i){int cnt0;for(int j0;jn;j){if(matrix[i][j]distanceThreshold){cnt;}}couti cntendl;if(cntmin){resi;mincnt;}}return res;}vectorvectorint getMatrix(int n,vectorvectorint edges){vectorvectorint res(n); //初始不可达for(int i0;in;i){res[i]getDistance(i,n,edges);}return res;}vectorint getDistance(int i,int n,vectorvectorint edges){vectorint res(n,10001);res[i]0;bool flagtrue;while(flag){flagfalse;for(int i0;iedges.size();i){if(res[edges[i][0]]edges[i][2]res[edges[i][1]]){res[edges[i][1]]res[edges[i][0]]edges[i][2];flagtrue;}else if(res[edges[i][1]]edges[i][2]res[edges[i][0]]){res[edges[i][0]]res[edges[i][1]]edges[i][2];flagtrue;}}}return res; }
}; 总结 把贝尔曼-福德算法和普里姆算法搞混了...... 代码可以优化一下,首先 最短距离超过阈值后就可返回,其次 a 节点到 b 节点的距离与 b 节点到 a 节点的距离相等,只需计算一次. 官方题解给出了分别基于 Dijkstra 算法和 Floyd 算法的代码.
