数据结构
网络
RDBMS
操作系统
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 编程
C++
C#
MongoDB
MySQL
Javascript
PHP
物理学
化学
生物学
数学
英语
经济学
心理学
社会学
服装设计
法律研究使用 C++ 查找邻居数量最少的城市（在阈值距离内）
假设有 n 个城市，编号从 0 到 n-1。如果我们有数组 edges，其中 edges[i] = [fromi, toi, weighti] 表示城市 fromi 和 toi 之间的双向加权边，并且给定整数距离阈值。我们需要找到一个城市，该城市可达的城市数量最少，并且这些城市之间的距离最多为距离阈值。如果有多个这样的城市，则返回编号最大的城市。
例如，如果输入为：
n 为 4，距离阈值也为 4，则输出将为 3。这是因为：
每个城市在距离阈值 = 4 时的邻近城市为：
C0 -> [C1, C2] C1 -> [C0, C2, C3] C2 -> [C0, C1, C3] C3 -> [C1, C2]
城市 0 和城市 3 在距离阈值 = 4 时各有 2 个邻近城市，但我们需要返回城市 3，因为它具有最大的编号。
为了解决这个问题，我们将遵循以下步骤：
定义一个 n x n 阶的方阵 dp，并将其填充为无穷大。
生成图的邻接矩阵（成本矩阵），并将其存储到 dp 中。
ret := 0 且 cnt := 无穷大。
对于 k 从 0 到 n – 1
对于 i 从 0 到 n – 1
对于 j 从 0 到 n – 1
如果 i = j，则继续进行下一次迭代。
如果 dp[i, j] > dp[i, k] + dp[k, j]，则
dp[j, i] := dp[i, k] + dp[k, j]
dp[i, j] := dp[i, k] + dp[k, j]
对于 i 从 0 到 n - 1
temp := 0
对于 j 从 0 到 n – 1
当 dp[i, j] <= t 时，temp := temp + 1，否则 temp 保持不变。
如果 temp <= cnt，则 cnt := temp 且 ret := i。
返回 ret。
示例（C++）
让我们看看下面的实现，以便更好地理解：
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
int findTheCity(int n, vector<vector<int>>& e, int t) {
vector < vector <int> > dp(n, vector <int>(n, 1e7));
for(int i = 0; i < e.size(); i++){
int u = e[i][0];
int v = e[i][1];
int w = e[i][2];
dp[u][v] = w;
dp[v][u] = w;
}
int ret = 0;
int cnt = INT_MAX;
for(int k = 0; k < n; k++){
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
if(i == j) continue;
if(dp[i][j] > dp[i][k] + dp[k][j]){
dp[j][i] = dp[i][j] = (dp[i][k] + dp[k][j]);
}
}
}
}
for(int i = 0; i < n; i++){
int temp = 0;
for(int j = 0; j < n; j++){
temp += (dp[i][j] <= t);
}
if(temp <= cnt){
cnt = temp;
ret = i;
}
}
return ret;
}
};
main(){
vector<vector<int>> v = {{0,1,3},{1,2,1},{1,3,4},{2,3,1}};
Solution ob;
cout << (ob.findTheCity(4, v, 4));
}输入
4 [[0,1,3],[1,2,1],[1,3,4],[2,3,1]] 4
输出
3
更新于： 2020-04-29
443 次浏览
广告