Description#
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:
![](https://spcdn.pages.dev/leetcode/problems/1334.Find%20the%20City%20With%20the%20Smallest%20Number%20of%20Neighbors%20at%20a%20Threshold%20Distance/images/find_the_city_01.png)
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:
![](https://spcdn.pages.dev/leetcode/problems/1334.Find%20the%20City%20With%20the%20Smallest%20Number%20of%20Neighbors%20at%20a%20Threshold%20Distance/images/find_the_city_02.png)
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
- All pairs
(fromi, toi)
are distinct.
Solutions#
Solution 1#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution:
def findTheCity(
self, n: int, edges: List[List[int]], distanceThreshold: int
) -> int:
def dijkstra(u: int) -> int:
dist = [inf] * n
dist[u] = 0
vis = [False] * n
for _ in range(n):
k = -1
for j in range(n):
if not vis[j] and (k == -1 or dist[k] > dist[j]):
k = j
vis[k] = True
for j in range(n):
# dist[j] = min(dist[j], dist[k] + g[k][j])
if dist[k] + g[k][j] < dist[j]:
dist[j] = dist[k] + g[k][j]
return sum(d <= distanceThreshold for d in dist)
g = [[inf] * n for _ in range(n)]
for f, t, w in edges:
g[f][t] = g[t][f] = w
ans, cnt = n, inf
for i in range(n - 1, -1, -1):
if (t := dijkstra(i)) < cnt:
cnt, ans = t, i
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
| class Solution {
private int n;
private int[][] g;
private int[] dist;
private boolean[] vis;
private final int inf = 1 << 30;
private int distanceThreshold;
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
this.n = n;
this.distanceThreshold = distanceThreshold;
g = new int[n][n];
dist = new int[n];
vis = new boolean[n];
for (var e : g) {
Arrays.fill(e, inf);
}
for (var e : edges) {
int f = e[0], t = e[1], w = e[2];
g[f][t] = w;
g[t][f] = w;
}
int ans = n, cnt = inf;
for (int i = n - 1; i >= 0; --i) {
int t = dijkstra(i);
if (t < cnt) {
cnt = t;
ans = i;
}
}
return ans;
}
private int dijkstra(int u) {
Arrays.fill(dist, inf);
Arrays.fill(vis, false);
dist[u] = 0;
for (int i = 0; i < n; ++i) {
int k = -1;
for (int j = 0; j < n; ++j) {
if (!vis[j] && (k == -1 || dist[k] > dist[j])) {
k = j;
}
}
vis[k] = true;
for (int j = 0; j < n; ++j) {
dist[j] = Math.min(dist[j], dist[k] + g[k][j]);
}
}
int cnt = 0;
for (int d : dist) {
if (d <= distanceThreshold) {
++cnt;
}
}
return cnt;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
int g[n][n];
int dist[n];
bool vis[n];
memset(g, 0x3f, sizeof(g));
for (auto& e : edges) {
int f = e[0], t = e[1], w = e[2];
g[f][t] = g[t][f] = w;
}
auto dijkstra = [&](int u) {
memset(dist, 0x3f, sizeof(dist));
memset(vis, 0, sizeof(vis));
dist[u] = 0;
for (int i = 0; i < n; ++i) {
int k = -1;
for (int j = 0; j < n; ++j) {
if (!vis[j] && (k == -1 || dist[j] < dist[k])) {
k = j;
}
}
vis[k] = true;
for (int j = 0; j < n; ++j) {
dist[j] = min(dist[j], dist[k] + g[k][j]);
}
}
return count_if(dist, dist + n, [&](int d) { return d <= distanceThreshold; });
};
int ans = n, cnt = n + 1;
for (int i = n - 1; ~i; --i) {
int t = dijkstra(i);
if (t < cnt) {
cnt = t;
ans = i;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
| func findTheCity(n int, edges [][]int, distanceThreshold int) int {
g := make([][]int, n)
dist := make([]int, n)
vis := make([]bool, n)
const inf int = 1e7
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = inf
}
}
for _, e := range edges {
f, t, w := e[0], e[1], e[2]
g[f][t], g[t][f] = w, w
}
dijkstra := func(u int) (cnt int) {
for i := range vis {
vis[i] = false
dist[i] = inf
}
dist[u] = 0
for i := 0; i < n; i++ {
k := -1
for j := 0; j < n; j++ {
if !vis[j] && (k == -1 || dist[j] < dist[k]) {
k = j
}
}
vis[k] = true
for j := 0; j < n; j++ {
dist[j] = min(dist[j], dist[k]+g[k][j])
}
}
for _, d := range dist {
if d <= distanceThreshold {
cnt++
}
}
return
}
ans, cnt := n, inf
for i := n - 1; i >= 0; i-- {
if t := dijkstra(i); t < cnt {
cnt = t
ans = i
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
const g: number[][] = Array.from({ length: n }, () => Array(n).fill(Infinity));
const dist: number[] = Array(n).fill(Infinity);
const vis: boolean[] = Array(n).fill(false);
for (const [f, t, w] of edges) {
g[f][t] = g[t][f] = w;
}
const dijkstra = (u: number): number => {
dist.fill(Infinity);
vis.fill(false);
dist[u] = 0;
for (let i = 0; i < n; ++i) {
let k = -1;
for (let j = 0; j < n; ++j) {
if (!vis[j] && (k === -1 || dist[j] < dist[k])) {
k = j;
}
}
vis[k] = true;
for (let j = 0; j < n; ++j) {
dist[j] = Math.min(dist[j], dist[k] + g[k][j]);
}
}
return dist.filter(d => d <= distanceThreshold).length;
};
let ans = n;
let cnt = Infinity;
for (let i = n - 1; i >= 0; --i) {
const t = dijkstra(i);
if (t < cnt) {
cnt = t;
ans = i;
}
}
return ans;
}
|
Solution 2#
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution:
def findTheCity(
self, n: int, edges: List[List[int]], distanceThreshold: int
) -> int:
g = [[inf] * n for _ in range(n)]
for f, t, w in edges:
g[f][t] = g[t][f] = w
for k in range(n):
g[k][k] = 0
for i in range(n):
for j in range(n):
# g[i][j] = min(g[i][j], g[i][k] + g[k][j])
if g[i][k] + g[k][j] < g[i][j]:
g[i][j] = g[i][k] + g[k][j]
ans, cnt = n, inf
for i in range(n - 1, -1, -1):
t = sum(d <= distanceThreshold for d in g[i])
if t < cnt:
cnt, ans = t, i
return ans
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
| class Solution {
public int findTheCity(int n, int[][] edges, int distanceThreshold) {
final int inf = 1 << 29;
int[][] g = new int[n][n];
for (var e : g) {
Arrays.fill(e, inf);
}
for (var e : edges) {
int f = e[0], t = e[1], w = e[2];
g[f][t] = w;
g[t][f] = w;
}
for (int k = 0; k < n; ++k) {
g[k][k] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
int ans = n, cnt = inf;
for (int i = n - 1; i >= 0; --i) {
int t = 0;
for (int d : g[i]) {
if (d <= distanceThreshold) {
++t;
}
}
if (t < cnt) {
cnt = t;
ans = i;
}
}
return ans;
}
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution {
public:
int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
int g[n][n];
memset(g, 0x3f, sizeof(g));
for (auto& e : edges) {
int f = e[0], t = e[1], w = e[2];
g[f][t] = g[t][f] = w;
}
for (int k = 0; k < n; ++k) {
g[k][k] = 0;
for (int i = 0; i < n; ++i) {
for (int j = 0; j < n; ++j) {
g[i][j] = min(g[i][j], g[i][k] + g[k][j]);
}
}
}
int ans = n, cnt = n + 1;
for (int i = n - 1; ~i; --i) {
int t = count_if(g[i], g[i] + n, [&](int x) { return x <= distanceThreshold; });
if (t < cnt) {
cnt = t;
ans = i;
}
}
return ans;
}
};
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
| func findTheCity(n int, edges [][]int, distanceThreshold int) int {
g := make([][]int, n)
const inf int = 1e7
for i := range g {
g[i] = make([]int, n)
for j := range g[i] {
g[i][j] = inf
}
}
for _, e := range edges {
f, t, w := e[0], e[1], e[2]
g[f][t], g[t][f] = w, w
}
for k := 0; k < n; k++ {
g[k][k] = 0
for i := 0; i < n; i++ {
for j := 0; j < n; j++ {
g[i][j] = min(g[i][j], g[i][k]+g[k][j])
}
}
}
ans, cnt := n, n+1
for i := n - 1; i >= 0; i-- {
t := 0
for _, x := range g[i] {
if x <= distanceThreshold {
t++
}
}
if t < cnt {
cnt, ans = t, i
}
}
return ans
}
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
const g: number[][] = Array.from({ length: n }, () => Array(n).fill(Infinity));
for (const [f, t, w] of edges) {
g[f][t] = g[t][f] = w;
}
for (let k = 0; k < n; ++k) {
g[k][k] = 0;
for (let i = 0; i < n; ++i) {
for (let j = 0; j < n; ++j) {
g[i][j] = Math.min(g[i][j], g[i][k] + g[k][j]);
}
}
}
let ans = n,
cnt = n + 1;
for (let i = n - 1; i >= 0; --i) {
const t = g[i].filter(x => x <= distanceThreshold).length;
if (t < cnt) {
cnt = t;
ans = i;
}
}
return ans;
}
|