There are n
cities numbered from 0
to n-1
. Given the array edges
where edges[i] = [fromi, toi, weighti]
represents a bidirectional and weighted edge between cities fromi
and toi
, and given the integer distanceThreshold
.
Return the city with the smallest number of cities that are reachable through some path and whose distance is at most distanceThreshold
, If there are multiple such cities, return the city with the greatest number.
Notice that the distance of a path connecting cities i and j is equal to the sum of the edges' weights along that 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 figure above describes the graph. The neighboring cities at a distanceThreshold = 4 for each city 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] Cities 0 and 3 have 2 neighboring cities at a distanceThreshold = 4, but we have to return city 3 since it has the greatest 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 figure above describes the graph. The neighboring cities at a distanceThreshold = 2 for 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] The city 0 has 1 neighboring city at a distanceThreshold = 2.
Constraints:
2 <= n <= 100
1 <= edges.length <= n * (n - 1) / 2
edges[i].length == 3
0 <= fromi < toi < n
1 <= weighti, distanceThreshold <= 10^4
(fromi, toi)
are distinct.struct Solution;
impl Solution {
fn find_the_city(n: i32, edges: Vec<Vec<i32>>, distance_threshold: i32) -> i32 {
let n = n as usize;
let mut dist = vec![vec![std::i32::MAX >> 2; n]; n];
for i in 0..n {
dist[i][i] = 0;
}
for e in edges {
let i = e[0] as usize;
let j = e[1] as usize;
let d = e[2];
dist[i][j] = d;
dist[j][i] = d;
}
for k in 0..n {
for i in 0..n {
for j in 0..n {
dist[i][j] = dist[i][j].min(dist[i][k] + dist[k][j]);
}
}
}
let mut min = (n, 0);
for i in 0..n {
let count = dist[i].iter().filter(|&&d| d <= distance_threshold).count() - 1;
if count <= min.0 {
min = (count, i);
}
}
min.1 as i32
}
}
#[test]
fn test() {
let n = 4;
let edges = vec_vec_i32![[0, 1, 3], [1, 2, 1], [1, 3, 4], [2, 3, 1]];
let distance_threshold = 4;
let res = 3;
assert_eq!(Solution::find_the_city(n, edges, distance_threshold), res);
let n = 5;
let edges = vec_vec_i32![
[0, 1, 2],
[0, 4, 8],
[1, 2, 3],
[1, 4, 2],
[2, 3, 1],
[3, 4, 1]
];
let distance_threshold = 2;
let res = 0;
assert_eq!(Solution::find_the_city(n, edges, distance_threshold), res);
}