公司网站建设要多少钱,微信小程序开发商家,网站建设合同服务范围,微信红包封面开放平台2023-11-14每日一题
一、题目编号
1334. 阈值距离内邻居最少的城市二、题目链接
点击跳转到题目位置
三、题目描述
有 n 个城市#xff0c;按从 0 到 n-1 编号。给你一个边数组 edges#xff0c;其中 edges[i] [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的…2023-11-14每日一题
一、题目编号
1334. 阈值距离内邻居最少的城市二、题目链接
点击跳转到题目位置
三、题目描述
有 n 个城市按从 0 到 n-1 编号。给你一个边数组 edges其中 edges[i] [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边距离阈值是一个整数 distanceThreshold。
返回能通过某些路径到达其他城市数目最少、且路径距离 最大 为 distanceThreshold 的城市。如果有多个这样的城市则返回编号最大的城市。
注意连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
示例 1
示例 2 提示
2 n 1001 edges.length n * (n - 1) / 2edges[i].length 30 fromi toi n1 weighti, distanceThreshold 104所有 (fromi, toi) 都是不同的。
四、解题代码
class Solution {#define maxn 101#define inf -1int Min(int a,int b){if(ainf){return b;}if(binf){return a;}return ab ? a:b;}int mat[maxn][maxn];int spfa(int n,int u,int dt){queueint q;int dist[maxn];memset(dist,inf,sizeof(dist));dist[u]0;q.push(u);while(!q.empty()){uq.front();q.pop();if(dist[u]dt){continue;}for(int i0;in;i){if(mat[u][i] inf){continue;}int todistdist[u]mat[u][i];if(dist[i]inf || todist dist[i]){dist[i]todist;q.push(i);}}}int cnt0;for(int i0;in;i){if(dist[i]!inf dist[i]dt){cnt;}}return cnt;}public:int findTheCity(int n, vectorvectorint edges, int dt) {memset(mat,inf,sizeof(mat));for(int i0;iedges.size();i){int uedges[i][0];int vedges[i][1];int wedges[i][2];mat[u][v]mat[v][u]Min(mat[u][v],w);}int Recnt111;int index-1;for(int in-1;i0;i--){int cntspfa(n,i,dt);if(cntRecnt){indexi;Recntcnt;}}return index;}
};五、解题思路
(1) 最短路径问题使用spfa算法解决。
