1334. The city with the fewest neighbors within the threshold distance
medium
There are n cities, numbered from 0 to n-1. Give you an edge array edges, where edges[i] = [fromi, toi, weighti] represents fromi and toi code> A bidirectional weighted edge between two cities, the distance threshold is an integer distanceThreshold.
Returns the city with the smallest number of other cities that can be reached through some path and the path distance maximum is distanceThreshold. If there are multiple such cities, the city with the highest number is returned.
Note that the distance of a path connecting cities i and j is equal to the sum of the weights of all edges along the path .
Example 1:
Input: n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4 Output: 3 Explanation: The city distribution map is as above. The neighbor cities within the threshold distance of each city distanceThreshold = 4 are: city 0 -> [city 1, city 2] City 1 -> [City 0, City 2, City 3] City 2 -> [City 0, City 1, City 3] City 3 -> [City 1, City 2] Both cities 0 and 3 have 2 neighbor cities within a threshold distance of 4, but we have to return city 3 because it has the highest number.
Example 2:
Input: n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1 ],[3,4,1]], distanceThreshold = 2 Output: 0 Explanation: The city distribution map is as above. The neighboring cities within the threshold distance distanceThreshold = 2 of each city are: city 0 -> [city 1] City 1 -> [City 0, City 4] City 2 -> [City 3, City 4] City 3 -> [City 2, City 4] City 4 -> [City 1, City 2, City 3] City 0 has only 1 neighbor city within a threshold distance of 2.
Tip:
2 <= n <= 1001 <= edges.length <= n * (n - 1) / 2edges[i].length == 30 <= fromi < toi < n1 <= weighti, distanceThreshold <= 10^4- All
(fromi, toi)are different.
Memory search (0x3f)
https://leetcode.cn/problems/find-the-city-with-the-smallest-number-of-neighbors-at-a-threshold-distance/solutions/2525946/dai-ni-fa-ming-floyd- suan-fa-cong-ji-yi-m8s51/?envType=daily-question &envId=2023-11-14
Interpretation of the question: For city i, find the shortest path length from i to other cities, and count how many shortest path lengths there are <= distanceThreshold
Inspiring thoughts:
class Solution {<!-- -->
public int findTheCity(int n, int[][] edges, int distanceThreshold) {<!-- -->
int[][] w = new int[n][n];
for(int[] row : w)
Arrays.fill(row, Integer.MAX_VALUE / 2);
for(int[] e : edges){<!-- -->
int x = e[0], y = e[1], wt = e[2];
w[x][y] = w[y][x] = wt;
}
int[][][] memo = new int[n][n][n];
int ans = 0;
int minCnt = n;
for(int i = 0; i < n; i + + ){<!-- -->
int cnt = 0;
for(int j = 0; j < n; j + + ){<!-- -->
if(j != i & amp; & amp; dfs(n-1, i, j, memo, w) <= distanceThreshold){<!-- -->
cnt + + ;
}
}
if(cnt <= minCnt){<!-- --> // When equal, take the largest i
minCnt = cnt;
ans = i;
}
}
return ans;
}
/**
Define dfs(k, i, j) to represent the length of the shortest path from i to j, and the intermediate node numbers of this shortest path are all <= k
Note that the intermediate node does not contain i and j
transfer
If k is not selected, then the numbers of the intermediate nodes are <= k-1, that is, dfs(k, i, j) = dfs(k-1, i, j)
Choose k, then the problem is decomposed into the shortest path from i to k, and the shortest path from k to j, since the intermediate nodes of these two shortest paths do not include k
All intermediate node labels are <= k-1, that is, dfs(k, i, j) = dfs(k-1, i, k) + dfs(k-1, k, k)
In these two cases, take the minimum value
Recursion boundary dfs(-1, i, j) = w[i][j], k=-1 means there is no intermediate node between i and j, and the shortest path length can only be the edge weight of i and j
If there is no edge connecting i and j, then w[i][j] = ∞
The recursive entry dfs(n-1, i, j) represents the shortest path length from i to j, k=n-1 is because the node numbers in this question are 0 to n-1
*/
public int dfs(int k, int i, int j, int[][][] memo, int[][] w){<!-- -->
if(k < 0)
return w[i][j];
if(memo[k][i][j] != 0)
return memo[k][i][j];
return memo[k][i][j] = Math.min(dfs(k-1, i, j, memo, w),
dfs(k-1, i, k, memo, w) + dfs(k-1, k, j, memo, w));
}
}
Retweet
Question: Why must k be enumerated at the outermost level?
Answer: Look carefully at the state transition equation above. To correctly calculate f[k + 1][i][j], you must first convert f[k][i][j] , f[k][i][k] and f[k][k][j] are calculated. Since we don’t know the size relationship between k and i,j, only by placing k in the outermost enumeration can we ensure that f[k][i][j], f[k][i][k] and f[k][k][j] Figure it out. By the way, for i and j, when calculating f[k + 1][i][j], f[k][.][.] has been fully calculated, so i and j can be enumerated in forward/reverse order.
class Solution {<!-- -->
/**
Bit 0 represents the case of k=-1
f[k + 1][i][j] = Math.min(f[k][i][j], f[k][i][k] + f[k][k][j])
Initialization f[0][i][j] = w[i][j]
*/
public int findTheCity(int n, int[][] edges, int distanceThreshold) {<!-- -->
int[][] w = new int[n][n];
for(int[] row : w)
Arrays.fill(row, Integer.MAX_VALUE / 2);
for(int[] e : edges){<!-- -->
int x = e[0], y = e[1], wt = e[2];
w[x][y] = w[y][x] = wt;
}
int[][][] f = new int[n + 1][n][n];
f[0] = w;
for(int k = 0; k < n; k + + ){<!-- -->
for(int i = 0; i < n; i + + ){<!-- -->
for(int j = 0; j < n; j + + ){<!-- -->
f[k + 1][i][j] = Math.min(f[k][i][j], f[k][i][k] + f[k][k][j]) ;
}
}
}
int ans = 0;
int minCnt = n;
for(int i = 0; i < n; i + + ){<!-- -->
int cnt = 0;
for(int j = 0; j < n; j + + ){<!-- -->
if(j != i & amp; & amp; f[n][i][j] <= distanceThreshold){<!-- -->
cnt + + ;
}
}
if(cnt <= minCnt){<!-- --> // When equal, take the largest i
minCnt = cnt;
ans = i;
}
}
return ans;
}
}
Status optimization
class Solution {<!-- -->
/**
When calculating f[k + 1], only f[k] will be used
f[k + 1][i][k] represents the length of the shortest path from i to k, and the intermediate node numbers of this shortest path are all <= k
Since the end point is k, the intermediate nodes must not contain k, so the intermediate node numbers are <= k-1
==> f[k + 1][i][k] = f[k][i][k]
In the same way, f[k + 1][k][j] = f[k][k][j]
*/
public int findTheCity(int n, int[][] edges, int distanceThreshold) {<!-- -->
int[][] w = new int[n][n];
for(int[] row : w)
Arrays.fill(row, Integer.MAX_VALUE / 2);
for(int[] e : edges){<!-- -->
int x = e[0], y = e[1], wt = e[2];
w[x][y] = w[y][x] = wt;
}
int[][] f = new int[n][n];
f = w;
for(int k = 0; k < n; k + + ){<!-- -->
for(int i = 0; i < n; i + + ){<!-- -->
for(int j = 0; j < n; j + + ){<!-- -->
f[i][j] = Math.min(f[i][j], f[i][k] + f[k][j]);
}
}
}
int ans = 0;
int minCnt = n;
for(int i = 0; i < n; i + + ){<!-- -->
int cnt = 0;
for(int j = 0; j < n; j + + ){<!-- -->
if(j != i & amp; & amp; f[i][j] <= distanceThreshold){<!-- -->
cnt + + ;
}
}
if(cnt <= minCnt){<!-- --> // When equal, take the largest i
minCnt = cnt;
ans = i;
}
}
return ans;
}
}