题目描述
有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。
返回在路径距离限制为 distanceThreshold 以内可到达城市最少的城市。如果有多个这样的城市，则返回编号最大的城市。
注意，连接城市 i 和 j 的路径的距离等于沿该路径的所有边的权重之和。
示例 1：
输入：n = 4, edges = [[0,1,3],[1,2,1],[1,3,4],[2,3,1]], distanceThreshold = 4
输出：3
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 4 内的邻居城市分别是：
城市 0 -> [城市 1, 城市 2]
城市 1 -> [城市 0, 城市 2, 城市 3]
城市 2 -> [城市 0, 城市 1, 城市 3]
城市 3 -> [城市 1, 城市 2]
城市 0 和 3 在阈值距离 4 以内都有 2 个邻居城市，但是我们必须返回城市 3，因为它的编号最大。
示例 2：
输入：n = 5, edges = [[0,1,2],[0,4,8],[1,2,3],[1,4,2],[2,3,1],[3,4,1]], distanceThreshold = 2
输出：0
解释：城市分布图如上。
每个城市阈值距离 distanceThreshold = 2 内的邻居城市分别是：
城市 0 -> [城市 1]
城市 1 -> [城市 0, 城市 4]
城市 2 -> [城市 3, 城市 4]
城市 3 -> [城市 2, 城市 4]
城市 4 -> [城市 1, 城市 2, 城市 3]
城市 0 在阈值距离 2 以内只有 1 个邻居城市。
提示：
2 <= n <= 1001 <= edges.length <= n * (n - 1) / 2edges[i].length == 30 <= fromi < toi < n1 <= weighti, distanceThreshold <= 10^4- 所有
(fromi, toi) 都是不同的。
解法
方法一：Dijkstra 算法
我们可以枚举每个城市 $i$ 作为起点，使用 Dijkstra 算法求出从 $i$ 到其他城市的最短距离，然后统计距离不超过阈值的城市个数，最后取最小的个数且编号最大的城市。
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为城市个数。
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;
}
|
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, edges, distanceThreshold) {
const g = Array.from({ length: n }, () => Array(n).fill(Infinity));
const dist = Array(n).fill(Infinity);
const vis = Array(n).fill(false);
for (const [f, t, w] of edges) {
g[f][t] = g[t][f] = w;
}
const dijkstra = u => {
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;
}
|
方法二：Floyd 算法
我们定义 $g[i][j]$ 表示城市 $i$ 到城市 $j$ 的最短距离，初始时 $g[i][j] = \infty$, $g[i][i] = 0$，然后我们遍历所有边，对于每条边 $(f, t, w)$，我们令 $g[f][t] = g[t][f] = w$。
接下来，我们用 Floyd 算法求出任意两点之间的最短距离。具体地，我们先枚举中间点 $k$，再枚举起点 $i$ 和终点 $j$，如果 $g[i][k] + g[k][j] \lt g[i][j]$，那么我们就用更短的距离 $g[i][k] + g[k][j]$ 更新 $g[i][j]$。
最后，我们枚举每个城市 $i$ 作为起点，统计距离不超过阈值的城市个数，最后取最小的个数且编号最大的城市。
时间复杂度 $O(n^3)$，空间复杂度 $O(n^2)$。其中 $n$ 为城市个数。
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;
}
|
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, edges, distanceThreshold) {
const g = 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;
}
|
Solution 3
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 | function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
const MAX = Number.POSITIVE_INFINITY;
const g = Array.from({ length: n }, () => new Map<number, number>());
const dist: number[] = Array(n).fill(MAX);
const vis: boolean[] = Array(n).fill(false);
for (const [f, t, w] of edges) {
g[f].set(t, w);
g[t].set(f, w);
}
const dijkstra = (u: number): number => {
dist.fill(MAX);
vis.fill(false);
dist[u] = 0;
const pq = new MinPriorityQueue();
pq.enqueue(u, 0);
while (!pq.isEmpty()) {
const u = pq.dequeue().element;
if (vis[u]) continue;
vis[u] = true;
for (const [v, w] of g[u]) {
if (vis[v]) continue;
const wNext = dist[u] + w;
if (wNext < dist[v]) {
dist[v] = wNext;
pq.enqueue(v, dist[v]);
}
}
}
return dist.filter(d => d <= distanceThreshold).length;
};
let ans = n;
let cnt = MAX;
for (let i = n - 1; i >= 0; --i) {
const 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 | export function findTheCity(n, edges, distanceThreshold) {
const MAX = Number.POSITIVE_INFINITY;
const g = Array.from({ length: n }, () => new Map());
const dist = Array(n).fill(MAX);
const vis = Array(n).fill(false);
for (const [f, t, w] of edges) {
g[f].set(t, w);
g[t].set(f, w);
}
const dijkstra = u => {
dist.fill(MAX);
vis.fill(false);
dist[u] = 0;
const pq = new MinPriorityQueue();
pq.enqueue(u, 0);
while (!pq.isEmpty()) {
const u = pq.dequeue().element;
if (vis[u]) continue;
vis[u] = true;
for (const [v, w] of g[u]) {
if (vis[v]) continue;
const wNext = dist[u] + w;
if (wNext < dist[v]) {
dist[v] = wNext;
pq.enqueue(v, dist[v]);
}
}
}
return dist.filter(d => d <= distanceThreshold).length;
};
let ans = n;
let cnt = MAX;
for (let i = n - 1; i >= 0; --i) {
const t = dijkstra(i);
if (t < cnt) {
cnt = t;
ans = i;
}
}
return ans;
}
|