【史上最全】涵盖所有「存图方式」与「最短路算法」

题目描述

这是 LeetCode 上的 「1334. 阈值距离内邻居最少的城市」 ，难度为 「中等」。

Tag : 「最短路」、「图」

有 个城市，按从 到 编号。

给你一个边数组 edges，其中 代表 和 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

返回能通过某些路径到达其他城市数目最少、且路径距离最大为 distanceThreshold 的城市。如果有多个这样的城市，则返回编号最大的城市。

注意，连接城市 和 的路径的距离等于沿该路径的所有边的权重之和。

示例 1： alt

输入：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： alt

输入：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 个邻居城市。

提示：

  • 所有 都是不同的。

基本分析

若能预处理图中任意两点 和 的最短距离 dist，那么统计每个点 在图中有多少满足 的点 即为答案。

于是问题转换为：「如何求解给定图中，任意两点的最短距离」。

存图

在学习最短路之前，我们先搞懂众多图论问题的前置 🧀 ：存图。

为了方便，我们约定 为点数， 为边数。

根据点和边的数量级关系，可以将图分成如下两类：

  • 稠密图：边数较多，边数接近于点数的平方，即
  • 稀疏图：边数较少，边数接近于点数，即

同时，根据「稠密图」还是「稀疏图」，我们有如下几种存图方式：

1. 邻接矩阵（稠密图）

这是一种使用二维矩阵来进行存图的方式。

// w[a][b] = c 代表从 a 到 b 有权重为 c 的边
int[][] g = new int[N][N];

// 加边操作
void add(int a, int b, int c) {
    g[a][b] = c;
}
2. 邻接表（稀疏图）

邻接表又叫「链式前向星」，是另一种常见的存图方式，实现代码与「使用数组存储单链表」一致（头插法）。

int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];

// 加边操作
void add(int a, int b, int c) {
    e[idx] = b;
    ne[idx] = he[a];
    w[idx] = c;
    he[a] = idx++;
}

首先 idx 是用来对边进行编号的，然后对存图用到的几个数组作简单解释：

  • he 数组：存储是某个节点所对应的边的集合（链表）的头结点；
  • e 数组：由于访问某一条边指向的节点；
  • ne 数组：由于是以链表的形式进行存边，该数组就是用于找到下一条边；
  • w 数组：用于记录某条边的权重为多少。

当我们想要遍历所有由 a 点发出的边时，可以使用如下方式：

for (int i = he[a]; i != -1; i = ne[i]) {
    int b = e[i], c = w[i]; // 存在由 a 指向 b 的边，权重为 c
}
3. 类

这是最简单，但使用频率最低的存图方式。

只有当我们需要确保某个操作复杂度为严格 时，才会考虑使用。

具体的，建立一个类来记录有向边信息：

class Edge {
    // 代表从 a 到 b 有一条权重为 c 的边
    int a, b, c;
    Edge(int _a, int _b, int _c) {
        a = _a; b = _b; c = _c;
    }
}

随后，使用诸如 List 的容器，存起所有边对象。在需要遍历所有边时，对容器进行进行遍历：

List<Edge> es = new ArrayList<>();

...

for (Edge e : es) {
    ...
}

综上，第 种方式，往往是 OJ 给我们边信息的方式，我们自己几乎不会用这种方式建图。

实际运用中，熟练掌握「如何根据点和边的数量级关系，来决定使用邻接矩阵（稠密图）还是邻接表（稀疏图）」即可。

Floyd（邻接矩阵）

Floyd 算法作为「多源汇最短路」算法，对于本题尤其适合。

Floyd 算法基于「动态规划」，其原始三维状态定义为 ，表示「所有从点 到点 ，且允许经过点集 的路径」中的最短距离。

状态转移方程：

代表从 到 但必然不经过点 的路径， 代表必然经过点 的路径，两者中取较小值更新 。

不难发现任意的 依赖于 ，可采用「滚动数组」的方式进行优化。

将 dist 声明为二维数组， 代表从点 到点 的最短距离，并采取 [枚举中转点 - 枚举起点 - 枚举终点] 三层循环的方式更新 。

如此一来，跑一遍 Floyd 算法便可得出任意两点的最短距离。

通过上述推导，不难发现，我们并没提及边权的正负问题，因此 Floyd 算法对边权的正负没有限制要求（可处理正负权边的图），且能利用 Floyd 算法可能够对图中负环进行判定。

Java 代码：

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] g = new int[n][n];
        // 初始化邻接矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = i == j ? 0 : 0x3f3f3f3f;
            }
        }
        // 存图
        for (int[] e : edges) {
            int a = e[0], b = e[1], c = e[2];
            g[a][b] = g[b][a] = Math.min(g[a][b], c);
        }
        // 最短路
        floyd(g);
        // 统计答案
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && g[i][j] <= distanceThreshold) cur++;
            }
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    void floyd(int[][] g) {
        int n = g.length;
        // floyd 基本流程为三层循环: [枚举中转点 - 枚举起点 - 枚举终点] => 松弛操作  
        for (int p = 0; p < n; p++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    g[i][j] = Math.min(g[i][j], g[i][p] + g[p][j]);
                }
            }
        }
    }
}

C++ 代码：

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> g(n, vector<int>(n, 0x3f3f3f3f));
        // 初始化邻接矩阵
        for (int i = 0; i < n; i++) g[i][i] = 0;
        // 存图
        for (const auto& e : edges) {
            int a = e[0], b = e[1], c = e[2];
            g[a][b] = g[b][a] = min(g[a][b], c);
        }
        // 最短路
        floyd(g);
        // 统计答案
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && g[i][j] <= distanceThreshold) cur++;
            }
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    void floyd(vector<vector<int>>& g) {
        int n = g.size();
        // floyd 基本流程为三层循环: [枚举中转点 - 枚举起点 - 枚举终点] => 松弛操作  
        for (int p = 0; p < n; p++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    g[i][j] = min(g[i][j], g[i][p] + g[p][j]);
                }
            }
        }
    }
};

Python 代码：

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        def floyd(g: List[List[int]]) -> None:
            n = len(g)
            # floyd 基本流程为三层循环: [枚举中转点 - 枚举起点 - 枚举终点] => 松弛操作
            for p in range(n):
                for i in range(n):
                    for j in range(n):
                        g[i][j] = min(g[i][j], g[i][p] + g[p][j])

        g = [[float('inf')] * n for _ in range(n)]
        # 初始化邻接矩阵
        for i in range(n):
            g[i][i] = 0
        # 存图
        for a, b, c in edges:
            g[a][b] = g[b][a] = min(g[a][b], c)
        # 最短路
        floyd(g)
        # 统计答案
        ans, cnt = -1, n + 10
        for i in range(n):
            cur = sum(1 for j in range(n) if i != j and g[i][j] <= distanceThreshold)
            if cur <= cnt:
                cnt, ans = cur, i
        return ans

TypeScript 代码：

function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
    const floyd = function (g: number[][]): void {
        const n = g.length;
        // floyd 基本流程为三层循环: [枚举中转点 - 枚举起点 - 枚举终点] => 松弛操作
        for (let p = 0; p < n; p++) {
            for (let i = 0; i < n; i++) {
                for (let j = 0; j < n; j++) {
                    g[i][j] = Math.min(g[i][j], g[i][p] + g[p][j]);
                }
            }
        }
    }

    const g = Array.from({ length: n }, () => Array(n).fill(0x3f3f3f3f));
    // 初始化邻接矩阵
    for (let i = 0; i < n; i++) g[i][i] = 0;
    // 存图
    for (const [a, b, c] of edges) g[a][b] = g[b][a] = Math.min(g[a][b], c);
    // 最短路
    floyd(g);
    // 统计答案
    let ans = -1, cnt = n + 10;
    for (let i = 0; i < n; i++) {
        let cur = 0;
        for (let j = 0; j < n; j++) {
            if (i !== j && g[i][j] <= distanceThreshold) cur++;
        }
        if (cur <= cnt) {
            cnt = cur; ans = i;
        }
    }
    return ans;
};
  • 时间复杂度：初始化邻接矩阵和建图复杂度为 ； floyd 算法复杂度为 ；统计答案复杂度为 ；整体复杂度为
  • 空间复杂度：

朴素 Dijkstra（邻接矩阵）

最为经典的「单源最短路」算法，通常搭配「邻接矩阵」使用，应用在边数较多的“稠密图”上。

朴素 Dijkstra 算法基于「贪心」，通过维护一维的距离数组 dist 实现， 表示从源点出发到点 的最短距离。

朴素 Dijkstra 算法在每一次迭代中，都选择 dist 中值最小的点进行松弛操作，逐渐扩展最短路径范围。

Java 代码：

class Solution {
    public int findTheCity(int n, int[][] edges, int distanceThreshold) {
        int[][] g = new int[n][n];
        // 初始化邻接矩阵
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                g[i][j] = i == j ? 0 : 0x3f3f3f3f;
            }
        }
        // 存图
        for (int[] e : edges) {
            int a = e[0], b = e[1], c = e[2];
            g[a][b] = g[b][a] = Math.min(g[a][b], c);
        }
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            // 单源最短路
            int[] dist = dijkstra(g, i);
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[j] <= distanceThreshold) cur++;
            }
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    int[] dijkstra(int[][] g, int x) {
        int n = g.length;
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        boolean[] vis = new boolean[n];
        int[] dist = new int[n];
        Arrays.fill(dist, 0x3f3f3f3f);
        // 只有起点最短距离为 0
        dist[x] = 0;
        // 有多少个点就迭代多少次
        for (int k = 0; k < n; k++) {
            // 每次找到「最短距离最小」且「未被更新」的点 t
            int t = -1;
            for (int i = 0; i < n; i++) {
                if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i;
            }
            // 标记点 t 为已更新
            vis[t] = true;
            // 用点 t 的「最小距离」更新其他点
            for (int i = 0; i < n; i++) dist[i] = Math.min(dist[i], dist[t] + g[t][i]);
        }
        return dist;
    }
}

C++ 代码：

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        vector<vector<int>> g(n, vector<int>(n, 0x3f3f3f3f));
        // 初始化邻接矩阵
        for (int i = 0; i < n; i++) g[i][i] = 0;
        // 存图
        for (const auto& e : edges) {
            int a = e[0], b = e[1], c = e[2];
            g[a][b] = g[b][a] = min(g[a][b], c);
        }
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            // 单源最短路
            vector<int> dist = dijkstra(g, i);
            int cur = count_if(dist.begin(), dist.end(), [distanceThreshold](int d) { return d <= distanceThreshold; });
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    vector<int> dijkstra(const vector<vector<int>>& g, int x) {
        int n = g.size();
        vector<bool> vis(n, false);
        vector<int> dist(n, 0x3f3f3f3f);
        // 只有起点最短距离为 0
        dist[x] = 0;
        // 有多少个点就迭代多少次
        for (int k = 0; k < n; k++) {
            // 每次找到「最短距离最小」且「未被更新」的点 t
            int t = -1;
            for (int i = 0; i < n; i++) {
                if (!vis[i] && (t == -1 || dist[i] < dist[t])) t = i;
            }
            // 标记点 t 为已更新
            vis[t] = true;
            // 用点 t 的「最小距离」更新其他点
            for (int i = 0; i < n; i++) dist[i] = min(dist[i], dist[t] + g[t][i]);
        }
        return dist;
    }
};

Python 代码：

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        def dijkstra(g, x):
            n = len(g)
            vis = [False] * n
            dist = [float('inf')] * n
            # 只有起点最短距离为 0
            dist[x] = 0
            # 有多少个点就迭代多少次
            for k in range(n):
                # 每次找到「最短距离最小」且「未被更新」的点 t
                t = min((i for i in range(n) if not vis[i]), key=lambda i: dist[i])
                # 标记点 t 为已更新
                vis[t] = True
                # 用点 t 的「最小距离」更新其他点
                for i in range(n):
                    dist[i] = min(dist[i], dist[t] + g[t][i])
            return dist

        g = [[float('inf')] * n for _ in range(n)]
        # 初始化邻接矩阵
        for i in range(n):
            g[i][i] = 0
        # 存图
        for a, b, c in edges:
            g[a][b] = g[b][a] = min(g[a][b], c)
        ans, cnt = -1, n + 10
        for i in range(n):
            # 单源最短路
            dist = dijkstra(g, i)
            cur = sum(1 for j in range(n) if i != j and dist[j] <= distanceThreshold)
            if cur <= cnt:
                cnt, ans = cur, i
        return ans

TypeScript 代码：

function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
    const dijkstra = function (g: number[][], x: number): number[]  {
        const n = g.length;
        const vis = Array(n).fill(false), dist = Array(n).fill(0x3f3f3f3f);
        // 只有起点最短距离为 0
        dist[x] = 0;
        // 有多少个点就迭代多少次
        for (let k = 0; k < n; k++) {
            // 每次找到「最短距离最小」且「未被更新」的点 t
            let t = -1;
            for (let i = 0; i < n; i++) {
                if (!vis[i] && (t === -1 || dist[i] < dist[t])) t = i;
            }
            // 标记点 t 为已更新
            vis[t] = true;
            // 用点 t 的「最小距离」更新其他点
            for (let i = 0; i < n; i++) dist[i] = Math.min(dist[i], dist[t] + g[t][i]);
        }
        return dist;
    }
    
    const g = Array.from({ length: n }, () => Array(n).fill(0x3f3f3f3f));
    // 初始化邻接矩阵
    for (let i = 0; i < n; i++) g[i][i] = 0;
    // 存图
    for (const [a, b, c] of edges) g[a][b] = g[b][a] = Math.min(g[a][b], c);
    let ans = -1, cnt = n + 10;
    for (let i = 0; i < n; i++) {
        // 单源最短路
        const dist = dijkstra(g, i);
        const cur = dist.filter(d => d <= distanceThreshold).length;
        if (cur <= cnt) {
            cnt = cur; ans = i;
        }
    }
    return ans;
};
  • 时间复杂度：初始化邻接矩阵和建图复杂度为 ；统计答案时，共执行 次朴素 dijkstra 算法，朴素 dijkstra 复杂度为 ，总复杂度为 。整体复杂度为
  • 空间复杂度：

堆优化 Dijkstra（邻接表）

堆优化 Dijkstra 算法与朴素 Dijkstra 算法都是「单源最短路」算法。

堆优化 Dijkstra 算法通过数据结构「优先队列（堆）」来优化朴素 Dijkstra 中的“找 dist 中值最小的点”的过程。

相比于复杂度与边数无关的 朴素 Dijkstra 算法，复杂度与边数相关的 堆优化 Dijkstra 算法更适合边较少的“稀疏图”。

Java 代码：

class Solution {
    int N = 110, M = N * N, INF = 0x3f3f3f3f, idx, n;
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        w[idx] = c;
        he[a] = idx++;
    }
    public int findTheCity(int _n, int[][] edges, int distanceThreshold) {
        n = _n;
        // 初始化链表头
        Arrays.fill(he, -1);
        // 存图
        for (int[] e : edges) {
            int a = e[0], b = e[1], c = e[2];
            add(a, b, c); add(b, a, c);
        }
        // 统计答案
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            // 单源最短路
            int[] dist = dijkstra(i);
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[j] <= distanceThreshold) cur++;
            }
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    int[] dijkstra(int x) {
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        int[] dist = new int[n];
        Arrays.fill(dist, 0x3f3f3f3f);
        boolean[] vis = new boolean[n];
        dist[x] = 0;
        // 使用「优先队列」存储所有可用于更新的点
        // 以 (点编号, 到起点的距离) 进行存储，优先弹出「最短距离」较小的点
        PriorityQueue<int[]> q = new PriorityQueue<>((a,b)->a[1]-b[1]);
        q.add(new int[]{x, 0});
        while (!q.isEmpty()) {
            // 每次从「优先队列」中弹出
            int[] poll = q.poll();
            int u = poll[0], step = poll[1];
            // 如果弹出的点被标记「已更新」，则跳过
            if (vis[u]) continue;
            // 标记该点「已更新」，并使用该点更新其他点的「最短距离」
            vis[u] = true;
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] <= dist[u] + w[i]) continue;
                dist[j] = dist[u] + w[i];
                q.add(new int[]{j, dist[j]});
            }
        }
        return dist;
    }
}

C++ 代码：

class Solution {
public:
    static const int N = 110, M = N * N;
    int he[N], e[M], ne[M], w[M], idx, n, INF = 0x3f3f3f3f;
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        w[idx] = c;
        he[a] = idx++;
    }
    int findTheCity(int _n, vector<vector<int>>& edges, int distanceThreshold) {
        n = _n;
        // 初始化链表头
        fill(he, he + n, -1);
        // 存图
        for (const auto& e : edges) {
            int a = e[0], b = e[1], c = e[2];
            add(a, b, c); add(b, a, c);
        }
        // 统计答案
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            // 单源最短路
            vector<int> dist = dijkstra(i);
            int cur = count_if(dist.begin(), dist.end(), [distanceThreshold](int d) { return d <= distanceThreshold; });
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    vector<int> dijkstra(int x) {
        // 起始先将所有的点标记为「未更新」和「距离为正无穷」
        vector<int> dist(n, INF);
        vector<bool> vis(n, false);
        dist[x] = 0;
        // 使用「优先队列」存储所有可用于更新的点
        // 以 (点编号, 到起点的距离) 进行存储，优先弹出「最短距离」较小的点
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;
        q.push({0, x});
        while (!q.empty()) {
            // 每次从「优先队列」中弹出
            auto [step, u] = q.top();
            q.pop();
            // 如果弹出的点被标记「已更新」，则跳过
            if (vis[u]) continue;
            // 标记该点「已更新」，并使用该点更新其他点的「最短距离」
            vis[u] = true;
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] <= dist[u] + w[i]) continue;
                dist[j] = dist[u] + w[i];
                q.push({dist[j], j});
            }
        }
        return dist;
    }
};

Python 代码：

import heapq

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        N, M, INF, idx = 110, 110 * 110, float('inf'), 0
        he, e, ne, w = [-1] * N, [0] * M, [0] * M, [0] * M

        def add(a, b, c):
            nonlocal idx
            e[idx] = b
            ne[idx] = he[a]
            w[idx] = c
            he[a] = idx
            idx += 1

        def dijkstra(x):
            # 起始先将所有的点标记为「未更新」和「距离为正无穷」
            dist = [float('inf')] * n
            vis = [False] * n
            dist[x] = 0
            # 使用「优先队列」存储所有可用于更新的点
            # 以 (点编号, 到起点的距离) 进行存储，优先弹出「最短距离」较小的点
            q = [(0, x)]
            heapq.heapify(q)
            while q:
                # 每次从「优先队列」中弹出
                step, u = heapq.heappop(q)
                # 如果弹出的点被标记「已更新」，则跳过
                if vis[u]: continue
                # 标记该点「已更新」，并使用该点更新其他点的「最短距离」
                vis[u] = True
                i = he[u]
                while i != -1:
                    j, c = e[i], w[i]
                    i = ne[i]
                    if dist[j] <= dist[u] + c: continue
                    dist[j] = dist[u] + c
                    heapq.heappush(q, (dist[j], j))
            return dist

        # 初始化链表头
        he = [-1] * N
        # 存图
        for a, b, c in edges:
            add(a, b, c)
            add(b, a, c)
        # 统计答案
        ans, cnt = -1, n + 10
        for i in range(n):
            # 单源最短路
            dist = dijkstra(i)
            cur = sum(1 for j in range(n) if i != j and dist[j] <= distanceThreshold)
            if cur <= cnt:
                cnt, ans = cur, i
        return ans
  • 时间复杂度：初始化邻接表和建图复杂度为 ；统计答案时，共执行 次堆优化 dijkstra 算法，堆优化 dijkstra 复杂度为 ，总复杂度为 。整体复杂度为
  • 空间复杂度：

Bellman Ford（类）

虽然题目规定了不存在「负权边」，但我们仍然可以使用可以在「负权图中求最短路」的 Bellman Ford 进行求解，该算法也是「单源最短路」算法，复杂度为 。

通常为了确保 ，可以单独建一个类代表边，将所有边存入集合中，在 次松弛操作中直接对边集合进行遍历。

由于本题边数量级为 ，共对 个点执行 Bellman Ford 算法，因此整体会去到 ，有 TLE 风险。

Java 代码：

class Solution {
    int n;
    public int findTheCity(int _n, int[][] edges, int distanceThreshold) {
        n = _n;
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            int[] dist = bf(edges, i);
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[j] <= distanceThreshold) cur++;
            }
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    int[] bf(int[][] edges, int x) {
        int[] dist = new int[n];
        // 起始先将所有的点标记为「距离为正无穷」, 只有起点最短距离为 0
        Arrays.fill(dist, 0x3f3f3f3f);
        dist[x] = 0;
        // 有多少个点就迭代多少次
        for (int k = 0; k < n; k++) {
            // 每次都使用上一次迭代的结果，执行松弛操作
            int[] prev = dist.clone();
            for (int[] e : edges) {
                int a = e[0], b = e[1], c = e[2];
                dist[b] = Math.min(dist[b], prev[a] + c);
                dist[a] = Math.min(dist[a], prev[b] + c);
            }
        }
        return dist;
    }
}

C++ 代码：

class Solution {
public:
    int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            vector<int> dist = bf(edges, i, n);
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[j] <= distanceThreshold) cur++;
            }
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    vector<int> bf(vector<vector<int>>& edges, int x, int n) {
        // 起始先将所有的点标记为「距离为正无穷」, 只有起点最短距离为 0
        vector<int> dist(n, 0x3f3f3f3f);
        dist[x] = 0;
        // 有多少个点就迭代多少次
        for (int k = 0; k < n; k++) {
            // 每次都使用上一次迭代的结果，执行松弛操作
            vector<int> prev = dist;
            for (const auto& e : edges) {
                int a = e[0], b = e[1], c = e[2];
                dist[b] = min(dist[b], prev[a] + c);
                dist[a] = min(dist[a], prev[b] + c);
            }
        }
        return dist;
    }
};

Python 代码：

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        def bf(edges: List[List[int]], x: int, n: int) -> List[int]:
            # 起始先将所有的点标记为「距离为正无穷」, 只有起点最短距离为 0
            dist = [float('inf')] * n
            dist[x] = 0
            # 有多少个点就迭代多少次
            for k in range(n):
                # 每次都使用上一次迭代的结果，执行松弛操作
                prev = dist.copy()
                for a, b, c in edges:
                    dist[b] = min(dist[b], prev[a] + c)
                    dist[a] = min(dist[a], prev[b] + c)
            return dist

        ans, cnt = -1, n + 10
        for i in range(n):
            dist = bf(edges, i, n)
            cur = sum(1 for j in range(n) if i != j and dist[j] <= distanceThreshold)
            if cur <= cnt:
                cnt, ans = cur, i
        return ans

TypeScript 代码：

function findTheCity(n: number, edges: number[][], distanceThreshold: number): number {
    const bf = function(x: number): number[] {
        // 起始先将所有的点标记为「距离为正无穷」, 只有起点最短距离为 0
        const dist = new Array(n).fill(0x3f3f3f3f);
        dist[x] = 0;
        // 有多少个点就迭代多少次
        for (let k = 0; k < n; k++) {
            // 每次都使用上一次迭代的结果，执行松弛操作
            const prev = dist.slice();
            for (const e of edges) {
                const a = e[0], b = e[1], c = e[2];
                dist[b] = Math.min(dist[b], prev[a] + c);
                dist[a] = Math.min(dist[a], prev[b] + c);
            }
        }
        return dist;
    }

    let ans = -1, cnt = n + 10;
    for (let i = 0; i < n; i++) {
        const dist = bf(i);
        let cur = 0;
        for (let j = 0; j < n; j++) {
            if (i !== j && dist[j] <= distanceThreshold) cur++;
        }
        if (cur <= cnt) {
            cnt = cur; ans = i;
        }
    }
    return ans;
};
  • 时间复杂度：统计答案时，共执行 次 Bellman Ford 算法， Bellman Ford 复杂度为 ，总复杂度为 。整体复杂度为
  • 空间复杂度：

SPFA（邻接表）

SPFA 也是一类能够处理「负权边」的单源最短路算法。

最坏情况下，复杂度为 ，在特定情况下，其效率优于 Dijkstra 算法，近似 。

基本执行流程如下：

  1. 用双端队列来维护待更新节点，初始将源点放入队列

  2. 每次从队列头中取出一个节点，对其所有相邻节点执行松弛操作

    1. 若某个相邻节点的最短距离发生了更新，且该节点不在队列中，将它加入队列中

  3. 重复以上步骤，直到队列为空

Java 代码：

class Solution {
    int N = 110, M = N * N, INF = 0x3f3f3f3f, idx, n;
    int[] he = new int[N], e = new int[M], ne = new int[M], w = new int[M];
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        w[idx] = c;
        he[a] = idx++;
    }
    public int findTheCity(int _n, int[][] edges, int distanceThreshold) {
        n = _n;
        // 初始化链表头
        Arrays.fill(he, -1);
        // 存图
        for (int[] e : edges) {
            int a = e[0], b = e[1], c = e[2];
            add(a, b, c); add(b, a, c);
        }
        // 统计答案
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            // 单源最短路
            int[] dist = spfa(i);
            int cur = 0;
            for (int j = 0; j < n; j++) {
                if (i != j && dist[j] <= distanceThreshold) cur++;
            }
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    int[] spfa(int x) {
        int[] dist = new int[n];
        boolean[] vis = new boolean[n];
        // 起始先将所有的点标记为「未入队」和「距离为正无穷」
        Arrays.fill(dist, INF);
        // 只有起点最短距离为 0
        dist[x] = 0;
        // 使用「双端队列」存储，存储的是点编号
        Deque<Integer> d = new ArrayDeque<>();
        // 将「源点/起点」进行入队，并标记「已入队」
        d.addLast(x);
        vis[x] = true;
        while (!d.isEmpty()) {
            // 每次从「双端队列」中取出，并标记「未入队」
            int u = d.pollFirst();
            vis[u] = false;
            // 尝试使用该点，更新其他点的最短距离
            // 如果更新的点，本身「未入队」则加入队列中，并标记「已入队」
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] <= dist[u] + w[i]) continue;
                dist[j] = dist[u] + w[i];
                if (vis[j]) continue;
                d.addLast(j);
                vis[j] = true;
            }
        }
        return dist;
    }
}

C++ 代码：

class Solution {
public:
    static const int N = 110, M = N * N;
    int he[N], e[M], ne[M], w[M], idx, n, INF = 0x3f3f3f3f;
    void add(int a, int b, int c) {
        e[idx] = b;
        ne[idx] = he[a];
        w[idx] = c;
        he[a] = idx++;
    }
    int findTheCity(int _n, vector<vector<int>>& edges, int distanceThreshold) {
        n = _n;
        fill(he, he + N, -1);
        for (const auto& e : edges) {
            int a = e[0], b = e[1], c = e[2];
            add(a, b, c); add(b, a, c);
        }
        int ans = -1, cnt = n + 10;
        for (int i = 0; i < n; i++) {
            vector<int> dist = spfa(i);
            int cur = count_if(dist.begin(), dist.end(), [&](int d) { return d != INF && d <= distanceThreshold; });
            if (cur <= cnt) {
                cnt = cur; ans = i;
            }
        }
        return ans;
    }
    vector<int> spfa(int x) {
        // 起始先将所有的点标记为「未入队」和「距离为正无穷」
        vector<int> dist(n, INF);
        vector<bool> vis(n, false);
        // 只有起点最短距离为 0
        dist[x] = 0;
        // 使用「双端队列」存储，存储的是点编号
        deque<int> d;
        // 将「源点/起点」进行入队，并标记「已入队」
        d.push_back(x);
        vis[x] = true;
        while (!d.empty()) {
            // 每次从「双端队列」中取出，并标记「未入队」
            int u = d.front();
            d.pop_front();
            vis[u] = false;
            // 尝试使用该点，更新其他点的最短距离
            // 如果更新的点，本身「未入队」则加入队列中，并标记「已入队」
            for (int i = he[u]; i != -1; i = ne[i]) {
                int j = e[i];
                if (dist[j] <= dist[u] + w[i]) continue;
                dist[j] = dist[u] + w[i];
                if (vis[j]) continue;
                d.push_back(j);
                vis[j] = true;
            }
        }
        return dist;
    }
};

Python 代码：

class Solution:
    def findTheCity(self, n: int, edges: List[List[int]], distanceThreshold: int) -> int:
        m, INF, idx = n * n, 0x3f3f3f3f, 0
        he, e, ne, w = [-1] * n, [0] * m, [0] * m, [0] * m

        def add(a: int, b: int, c: int):
            nonlocal idx
            e[idx] = b
            ne[idx] = he[a]
            w[idx] = c
            he[a] = idx
            idx += 1

        def spfa(x: int) -> List[int]:
            # 起始先将所有的点标记为「未入队」和「距离为正无穷」
            dist = [INF] * n
            vis = [False] * n
            # 只有起点最短距离为 0
            dist[x] = 0
            # 使用「双端队列」存储，存储的是点编号
            d = deque()
            # 将「源点/起点」进行入队，并标记「已入队」
            d.append(x)
            vis[x] = True
            while d:
                # 每次从「双端队列」中取出，并标记「未入队」
                u = d.popleft()
                vis[u] = False
                i = he[u]
                # 尝试使用该点，更新其他点的最短距离
                # 如果更新的点，本身「未入队」则加入队列中，并标记「已入队」
                while i != -1:
                    j, c = e[i], w[i]
                    i = ne[i]
                    if dist[j] <= dist[u] + c: continue
                    dist[j] = dist[u] + c
                    if vis[j]: continue
                    d.append(j)
                    vis[j] = True
            return dist

        for a, b, c in edges:
            add(a, b, c)
            add(b, a, c)

        ans, cnt = -1, n + 10
        for i in range(n):
            dist = spfa(i)
            cur = sum(1 for d in dist if d != INF and d <= distanceThreshold)
            if cur <= cnt:
                cnt, ans = cur, i
        return ans
  • 时间复杂度：统计答案时，共执行 次 spfa 算法， spfa 复杂度为 ，总复杂度为 。整体复杂度为
  • 空间复杂度：

最后

这是我们「刷穿 LeetCode」系列文章的第 No.1334 篇，系列开始于 2021/01/01，截止于起始日 LeetCode 上共有 1916 道题目，部分是有锁题，我们将先把所有不带锁的题目刷完。

在这个系列文章里面，除了讲解解题思路以外，还会尽可能给出最为简洁的代码。如果涉及通解还会相应的代码模板。

为了方便各位同学能够电脑上进行调试和提交代码，我建立了相关的仓库：https://github.com/SharingSource/LogicStack-LeetCode 。

在仓库地址里，你可以看到系列文章的题解链接、系列文章的相应代码、LeetCode 原题链接和其他优选题解。

更多更全更热门的「笔试/面试」相关资料可访问排版精美的 合集新基地 🎉🎉

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/143683.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

ts+vite报错：找不到模块“/src/.../...”或其相应的类型声明

ts+vite报错：找不到模块“/src/.../...”或其相应的类型声明

问题描述 vuets项目开发时&#xff0c;通过绝对路径引入模块&#xff0c;发现ts报错&#xff1a;找不到模块“/src/script/game”或其相应的类型声明。ts(2307)。但是项目能正常运行。 原因 由于并没有配置代表src&#xff0c;结果通过绝对路径引入还是报错&#xff0c;于是换…
阅读更多...
国产源代码扫描工具DMSCA扫描出的报告优秀吗？

国产源代码扫描工具DMSCA扫描出的报告优秀吗？

在源代码扫描工具中&#xff0c;扫描报告是非常具有参考意义的&#xff0c;一方面可以了解我们开发项目的漏洞情况&#xff0c;另一方面也可以针对扫出的漏洞进行修复&#xff0c;确保开发出安全可靠的软件。误报和漏报是一个非常重要的参考指标。 国产源代码扫描工具DMSCA&am…
阅读更多...
andorid 日历选择器

andorid 日历选择器

先看效果图&#xff1a; 主要代码 package com.example.flyimport android.annotation.SuppressLint import android.content.Context import android.graphics.Color import android.util.AttributeSet import android.view.LayoutInflater import android.view.View import…
阅读更多...
算法通关村第九关-青铜挑战二分查找算法

算法通关村第九关-青铜挑战二分查找算法

大家好我是苏麟 , 今天聊聊二分查找算法 ...... 普通查找 普通查找就是最简单的循环查找 , 无论是有席的还是无席的都可以&#xff0c;也不需要排序&#xff0c;只需要一个个对比即可&#xff0c;但其实效率很低 : public int search(int[] arr, int target) {for (int i 0;…
阅读更多...
GEE遥感云大数据林业应用典型案例实践及GPT模型应用

GEE遥感云大数据林业应用典型案例实践及GPT模型应用

近年来遥感技术得到了突飞猛进的发展&#xff0c;航天、航空、临近空间等多遥感平台不断增加&#xff0c;数据的空间、时间、光谱分辨率不断提高&#xff0c;数据量猛增&#xff0c;遥感数据已经越来越具有大数据特征。遥感大数据的出现为相关研究提供了前所未有的机遇&#xf…
阅读更多...
SPSS时间序列分析：谱分析

SPSS时间序列分析：谱分析

前言&#xff1a; 本专栏参考教材为《SPSS22.0从入门到精通》&#xff0c;由于软件版本原因&#xff0c;部分内容有所改变&#xff0c;为适应软件版本的变化&#xff0c;特此创作此专栏便于大家学习。本专栏使用软件为&#xff1a;SPSS25.0 本专栏所有的数据文件请点击此链接下…
阅读更多...
eVTOL分布式电推进（DEP）动力测试系统

eVTOL分布式电推进（DEP）动力测试系统

产品简介 分布式电推进&#xff08;DEP&#xff09;技术因其灵活多变的机械电气化设计&#xff0c;可以大大提升动力系统的安全性冗余&#xff0c;极大增强飞行过程中的可操控性&#xff0c;同时可以有效降低本机噪音&#xff0c;最大限度提升动力系统的能源使用效率等优势&am…
阅读更多...
释放潜能，加速创新 | 低代码赋能企业数据资产管理（附案例）

释放潜能，加速创新 | 低代码赋能企业数据资产管理（附案例）

在当今数字化快速发展的时代&#xff0c;企业要想保持竞争力&#xff0c;就必须紧跟潮流&#xff0c;不断进行自我革新。其中&#xff0c;数字化转型已成为企业发展的重要一环&#xff0c;在这个过程中&#xff0c;数据资产作为企业核心竞争力的关键组成部分&#xff0c;其管理…
阅读更多...
​Distil-Whisper：比Whisper快6倍，体积小50%的语音识别模型

​Distil-Whisper：比Whisper快6倍，体积小50%的语音识别模型

内容来源&#xff1a;xiaohuggg Distil-Whisper&#xff1a;比Whisper快6倍&#xff0c;体积小50%的语音识别模型 ​该模型是由Hugging Face团队开发&#xff0c;它在Whisper核心功能的基础上进行了优化和简化&#xff0c;体积缩小了50%。速度提高了6倍。并且在分布外评估集上…
阅读更多...
条码管理在WMS仓储管理系统中的应用

条码管理在WMS仓储管理系统中的应用

在当今快节奏的商业环境中&#xff0c;仓储管理对于企业的运营和成本控制具有重要意义。为了提高管理效率和准确性&#xff0c;越来越多的企业开始采用条码管理WMS系统。本文将介绍这一系统的应用场景、条码引入WMS仓储管理系统的步骤以及其在仓储管理中的应用价值&#xff0c;…
阅读更多...
如何使用功率放大器

如何使用功率放大器

功率放大器是一种用于放大电流或电压的重要设备&#xff0c;广泛应用于音频、通信、无线电和电力等领域。正确地使用功率放大器可以确保其正常工作并获得满意的性能。下面西安安泰将介绍使用功率放大器的一般步骤和注意事项。 首先&#xff0c;了解功率放大器的规格和特性非常重…
阅读更多...
uniapp运行到安卓模拟器一直在“同步手机端程序文件完成“界面解决办法

uniapp运行到安卓模拟器一直在“同步手机端程序文件完成“界面解决办法

如果你是用的模拟器是android studio创建的模拟器&#xff0c;那么你需要新创建一个android11 x86架构的模拟器&#xff1a; 创建完成后&#xff0c;启动模拟器&#xff1a; 然后在hbuilder中重新运行到这个模拟器就可以了&#xff1a; 运行结果&#xff1a; 如果你是用安…
阅读更多...
如何在 macOS 中删除 Time Machine 本地快照

如何在 macOS 中删除 Time Machine 本地快照

看到这个可用82GB&#xff08;458.3MB可清除&#xff09; 顿时感觉清爽&#xff0c;之前的还是可用82GB&#xff08;65GB可清除&#xff09;&#xff0c;安装个xcode都安装不上&#xff0c;费解半天&#xff0c;怎么都解决不了这个问题&#xff0c;就是买磁盘情理软件也解决不了…
阅读更多...
leetcode:LCR 133. 位 1 的个数(python3解法)

leetcode:LCR 133. 位 1 的个数(python3解法)

难度&#xff1a;简单 编写一个函数&#xff0c;输入是一个无符号整数&#xff08;以二进制串的形式&#xff09;&#xff0c;返回其二进制表达式中数字位数为 1 的个数&#xff08;也被称为 汉明重量).&#xff09;。 提示&#xff1a; 请注意&#xff0c;在某些语言&#xff…
阅读更多...
STM32 I2C详解

STM32 I2C详解

STM32 I2C详解 I2C简介 I2C&#xff08;Inter IC Bus&#xff09;是由Philips公司开发的一种通用数据总线 两根通信线&#xff1a; SCL&#xff08;Serial Clock&#xff09;串行时钟线&#xff0c;使用同步的时序&#xff0c;降低对硬件的依赖&#xff0c;同时同步的时序稳定…
阅读更多...
网网络安全基础之php开发 文件读取、写入功能的实现

网网络安全基础之php开发 文件读取、写入功能的实现

前言 续之前的系列&#xff0c;这里php开发的文件操作的内容读取以及文本写入的部分 文件读取代码的实现 css代码 本系列的php博客都是这个css&#xff0c;名字都是index.css /* css样式初始化 */ * {font-family: Poppins, sans-serif;margin: 0;padding: 0;box-sizing: …
阅读更多...
新版软考高项试题分析精选（二）

新版软考高项试题分析精选（二）

请点击↑关注、收藏&#xff0c;本博客免费为你获取精彩知识分享&#xff01;有惊喜哟&#xff01;&#xff01; 1、除了测试程序之外&#xff0c;黑盒测试还适用于测试&#xff08; &#xff09;阶段的软件文档。 A.编码 B.总体设计 D.数据库设计 C.软件需求分析 答案&a…
阅读更多...
基于vue 2.0的H5页面中使用高德地图定位，搜索周边商户，覆盖物标记

基于vue 2.0的H5页面中使用高德地图定位，搜索周边商户，覆盖物标记

基于vue的H5页面中使用高德地图定位&#xff0c;搜索周边商户&#xff0c;覆盖物标记 首先安装高德地图插件 npm i amap/amap-jsapi-loader --save地图承载容器 <template><div id"container"></div> </template>地图容器样式 <style…
阅读更多...
C语言精选练习题：（7）计算最大值和最小值的差

C语言精选练习题：（7）计算最大值和最小值的差

每日一言 欲把西湖比西子&#xff0c;淡妆浓抹总相宜。 --饮湖上初晴后雨二首其二 题目 输入10个整数&#xff0c;找出其中的最大和最小值&#xff0c;计算两者的差&#xff0c;并打印出来 解题思路 创建一个数组用循环将10个整数存到数组中用打擂台的方式求出最大和最小值打…
阅读更多...
ModuleNotFoundError_ No module named ‘Crypto‘

ModuleNotFoundError_ No module named ‘Crypto‘

当要使用 python 进行加密数据的时候报错了 from Crypto.Util.Padding import pad, unpad from Crypto.Cipher import AES报错 File "F:\huisu.py", line 1, in <module>from Crypto.Util.Padding import pad, unpad ModuleNotFoundError: No module named Cr…
阅读更多...
最新文章

Copyright @ 2022~2023