資料結構
網路
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 次瀏覽
廣告