数据结构与算法：图论——最短路径

最短路径

先给出一些leetcode算法题，以后遇见了相关题目再往上增加

最短路径的4个常用算法是Floyd、Bellman-Ford、SPFA、Dijkstra。不同应用场景下，应有选择地使用它们：

  • 图的规模小，用Floyd。若边的权值有负数，需要判断负圈。
  • 图的规模大，且边的权值非负，用Dijkstra。
  • 图的规模大，且边的权值有负数，用SPFA，需要判断负圈。
结点N、边M边权值选用算法数据结构
n<200允许有负Floyd邻接矩阵
n×m<107允许有负Bellman-Ford邻接表
更大有负SPFA邻接表、前向星
更大无负数Dijkstra邻接表、前向星

2.1、Floyd算法

  • Floyed算法：主要是构建 二维矩阵：dp[i][j] 表示从节点 i 到节点 j 最短距离
  • 初始化矩阵时：有方向性、并且同一节点的最短距离为0
//  floyed 算法vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 2));for (auto a : times) {dp[a[0]][a[1]] = a[2];}for (int i = 0; i <= n; i++) {dp[i][i] = 0;}for (int k = 0; k <= n; k++) for (int i = 0; i <= n; i++) for (int j = 0; j <= n; j++) if (dp[i][j] > dp[i][k] + dp[k][j]) dp[i][j] = dp[i][k] + dp[k][j];

1、743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

img

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

提示：

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • 所有 (ui, vi) 对都 互不相同（即，不含重复边）
//  floyed 算法
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<vector<int>> dp(n + 1, vector<int>(n + 1, INT_MAX / 2));for (auto a : times) {dp[a[0]][a[1]] = a[2];}for (int i = 0; i <= n; i++) {dp[i][i] = 0;}for (int k = 0; k <= n; k++) {for (int i = 0; i <= n; i++) {for (int j = 0; j <= n; j++) {if (dp[i][j] > dp[i][k] + dp[k][j]) {dp[i][j] = dp[i][k] + dp[k][j];}}}}int res = 0;for (int i = 1; i <= n; i++) {if (dp[k][i] == INT_MAX / 2)return -1;res = max(res, dp[k][i]);}return res;}
};

2、1334. 阈值距离内邻居最少的城市

  • 这个用floyed直接算即可。无向图构造矩阵时重复操作即可

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

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

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

示例 1：

image-20240508214812051

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

image-20240508214822340

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

class Solution {
public:int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {vector<vector<int>> dp(n, vector<int>(n, INT_MAX / 2));for (auto a : edges) {dp[a[0]][a[1]] = a[2];dp[a[1]][a[0]] = a[2];}for (int k = 0; k < n; k++)for (int i = 0; i < n; i++)for (int j = 0; j < n; j++)if (dp[i][j] > dp[i][k] + dp[k][j])dp[i][j] = dp[i][k] + dp[k][j];// floyed计算完毕，取次数判断即可vector<int> cnt(n, 0);for (int i = 0; i < n; i++) {for (int j = 0; j < n; j++) {if (i == j)continue;if (dp[i][j] <= distanceThreshold)cnt[i]++;}}int min = *min_element(cnt.begin(), cnt.end());int res;for (int i = n - 1; i >= 0; i--) {if (min == cnt[i]) {res = i;break;}}return res;}
};

2.2、BellmanFord算法

  • Bellman-ford算法的思路也很简单，直接就是两层循环，内层循环所有边，外层循环就是循环所有边的次数。
  • 时间复杂度是O(n*m)显然不如dijkstra快
  • 优点：它可以处理负权边和负权环的情况。并且可以处理限制次数的问题。
//  dp[j] 表示节点k到j的最短路径：并且注意每次更新最短路径，是在上一次的dp上更新：
//  a[0] 表示起始节点；a[1] 表示最终节点；a[2]表示a[0]到a[1] 的距离大小。
//  a[0]->a[1]距离为a[2]：所以每次更新的都是 dp[a[1]] ，但是需要上一次的整体的predp，来取a[0]节点的最短距离// 最标准的形式有前一个的最小距离的predp
int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<int> dp(n+1,INT_MAX/2);dp[k] = 0;bool flag;while(1){flag = true;vector<int> predp(dp);for(auto a:times){if(dp[a[1]] > predp[a[0]]+a[2]){flag = false;dp[a[1]] = predp[a[0]]+a[2];}}if(flag)	break;}int res = *max_element(dp.begin()+1,dp.end());return res==INT_MAX/2?-1:res;}//	 然而没有predp也可以，省下来空间
int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<int> dp(n+1,INT_MAX/2);dp[k ] = 0;bool flag;while(1){flag = true;for(auto a:times){if(dp[a[1]] > dp[a[0]]+a[2]){flag = false;dp[a[1]] = dp[a[0]]+a[2];}}if(flag) break;}int res = *max_element(dp.begin()+1,dp.end());return res==INT_MAX/2?-1:res;
}

1、743. 网络延迟时间

示例 1：

img

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

// BellmanFord算法  算法复杂度为O（m*n）
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<int> dp(n+1,INT_MAX/2);dp[k ] = 0;bool flag;while(1){flag = true;// vector<int> predp(dp);for(auto a:times){if(dp[a[1]] > dp[a[0]]+a[2]){flag = false;dp[a[1]] = dp[a[0]]+a[2];}}if(flag) break;}int res = *max_element(dp.begin()+1,dp.end());return res==INT_MAX/2?-1:res;}
};

2、787. K 站中转内最便宜的航班

  • 经典使用BellmanFord算法题目：最多经过 k 站中转的路线

有 n 个城市通过一些航班连接。给你一个数组 flights ，其中 flights[i] = [fromi, toi, pricei] ，表示该航班都从城市 fromi 开始，以价格 pricei 抵达 toi。

现在给定所有的城市和航班，以及出发城市 src 和目的地 dst，你的任务是找到出一条最多经过 k 站中转的路线，使得从 src 到 dst 的 价格最便宜 ，并返回该价格。 如果不存在这样的路线，则输出 -1。

示例 1：

img

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 1
输出: 200
解释: 
城市航班图如下
从城市 0 到城市 2 在 1 站中转以内的最便宜价格是 200，如图中红色所示。

示例 2：

img

输入: 
n = 3, edges = [[0,1,100],[1,2,100],[0,2,500]]
src = 0, dst = 2, k = 0
输出: 500
解释: 
城市航班图如下
从城市 0 到城市 2 在 0 站中转以内的最便宜价格是 500，图中蓝色所示。

提示：

  • 1 <= n <= 100
  • 0 <= flights.length <= (n * (n - 1) / 2)
  • flights[i].length == 3
  • 0 <= fromi, toi < n
  • fromi != toi
  • 1 <= pricei <= 104
  • 航班没有重复，且不存在自环
  • 0 <= src, dst, k < n
  • src != dst
/*BellmanFord算法:：外层的路径就是中转的次数，但是注意K++；是中转1此，那么可以使用两条路径使用BellmanFord算法最标准形式：使用predp形式
*/
class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k) {vector<int> dp(n, 1e5+1);dp[src] = 0;k++;while (k--) {vector<int> predp(dp);// 这里最好加&可以大大提高速度for (auto &a : flights) {if(dp[a[1]]>predp[a[0]]+a[2])dp[a[1]] =predp[a[0]]+a[2];}}return dp[dst] ==  1e5+1? -1 : dp[dst];}
};
/*不使用BellmanFord算法最标准形式：无predp形式无法准确得到中转次数：结果不对，但是不考虑次数的话，也能得到最短距离
*/// 结果不对
class Solution {
public:int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst,int k) {vector<int> dp(n, 1e5+1);dp[src] = 0;k++;while (k--) {// vector<int> predp(dp);for (auto &a : flights) {if(dp[a[1]]>dp[a[0]]+a[2])dp[a[1]] =dp[a[0]]+a[2];}}return dp[dst] ==  1e5+1? -1 : dp[dst];}
};

3、1514. 概率最大的路径

  • 本题重点是无向图：两边都要操作一次，重复操作即可
  • 无向图：说白了就是条件是有向图的两倍，给反转前后节点即可

给你一个由 n 个节点（下标从 0 开始）组成的无向加权图，该图由一个描述边的列表组成，其中 edges[i] = [a, b] 表示连接节点 a 和 b 的一条无向边，且该边遍历成功的概率为 succProb[i] 。

指定两个节点分别作为起点 start 和终点 end ，请你找出从起点到终点成功概率最大的路径，并返回其成功概率。

如果不存在从 start 到 end 的路径，请 返回 0 。只要答案与标准答案的误差不超过 1e-5 ，就会被视作正确答案。

示例 1：

img

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.2], start = 0, end = 2
输出：0.25000
解释：从起点到终点有两条路径，其中一条的成功概率为 0.2 ，而另一条为 0.5 * 0.5 = 0.25

示例 2：

img

输入：n = 3, edges = [[0,1],[1,2],[0,2]], succProb = [0.5,0.5,0.3], start = 0, end = 2
输出：0.30000

示例 3：

img

输入：n = 3, edges = [[0,1]], succProb = [0.5], start = 0, end = 2
输出：0.00000
解释：节点 0 和 节点 2 之间不存在路径

提示：

  • 2 <= n <= 10^4
  • 0 <= start, end < n
  • start != end
  • 0 <= a, b < n
  • a != b
  • 0 <= succProb.length == edges.length <= 2*10^4
  • 0 <= succProb[i] <= 1
  • 每两个节点之间最多有一条边
class Solution {
public:double maxProbability(int n, vector<vector<int>>& edges,vector<double>& succProb, int start_node,int end_node) {vector<double> dp(n, 0);dp[start_node] = 1;while (1) {bool flag = true;for (int i = 0; i < succProb.size(); i++) {// 双向图：反转前后再操作一次即可if (dp[edges[i][1]] < dp[edges[i][0]] * succProb[i]) {flag = false;dp[edges[i][1]] = dp[edges[i][0]] * succProb[i];}if (dp[edges[i][0]] < dp[edges[i][1]] * succProb[i]) {flag = false;dp[edges[i][0]] = dp[edges[i][1]] * succProb[i];}}if (flag)   break;}return dp[end_node];}
};

3、1334. 阈值距离内邻居最少的城市

  • 这个用floyed直接算即可。使用bellmanFord可以做

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

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

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

示例 1：

image-20250502234625382

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

image-20250502234614892

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

class Solution {
public:int targetnum(int n, vector<vector<int>>& edges, int distanceThreshold,int k) {vector<int> dp(n, INT_MAX / 2);dp[k] = 0;while (1) {bool flag = true;vector<int> predp(dp);for (auto& a : edges) {if (dp[a[1]] > predp[a[0]] + a[2]) {flag = false;dp[a[1]] = predp[a[0]] + a[2];}if (dp[a[0]] > predp[a[1]] + a[2]) {flag = false;dp[a[0]] = predp[a[1]] + a[2];}}if (flag)break;}int res = 0;/*这里注意：这个是排除本身for (int i = 0; i < n; i++) {if (i == k)continue;if (dp[i] <= distanceThreshold) {res++;}}若改成：只要碰到i!=k，则跳出这个for循环，后面都不执行了for (int i = 0; i < n && i!=k; i++) {if (dp[i] <= distanceThreshold) {res++;}}*/for (int i = 0; i < n; i++) {if (i == k)continue;if (dp[i] <= distanceThreshold) {res++;}}return res;}// 找到最右边的最小值及坐标。int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {int min_num = 200;int res = 0;for(int i = 0;i<n;i++){int mid = BellmabFord( n, edges, i, distanceThreshold);if(mid<=min_num){min_num = mid;res = i; }}return res;}// 直观但臃肿。int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {int minn = INT_MAX / 2;vector<int> res;for (int i = 0; i < n; i++) {res.push_back(targetnum(n, edges, distanceThreshold, i));}int sul = 0;int minnub = *min_element(res.begin(), res.end());for (int i = n - 1; i >= 0; i--) {if (res[i] == minnub) {sul = i;break;}}return sul;}
};

2.3、dijkstra算法

  • 基础型：图的规模大，且边的权值非负，用Dijkstra。时间复杂度O(N*N)。可以看出时间复杂度 只和 n （节点数量）有关系。
// dijkstra算法基础版/*基础版：适用于题目中给出距离矩阵，给出矩阵
*/
vector<int> dijkstra(vector<vector<int>>& value, int start) {//需要一个二维矩阵从0到n，0基本上没有用，无关的都是INT_MAX / 2//对角线为0//返回了一个value[i][j]表示从i到j的最短路径，但是i，j不为0int len = value.size();      // len = n + 1;int n = len - 1;vector<int> res(len, INT_MAX);res[start] = 0;vector<bool> visit(len, false);for (int i = 1; i <= n; i++) {// 找到最小蓝的位置int minbule = 0;for (int j = 1; j <= n; j++) {if (!visit[j] && res[minbule] > res[j]) {minbule = j;}}if(visited[blue]) continue;// 把最小蓝变成白色visit[minbule] = true;// 更新所有最短距离for (int j = 1; j <= n; j++) {res[j] = min(res[j], res[minbule] + value[minbule][j]);}}return res;
}
  • 堆优化型：使用边数，边数少的，堆优化比较好。时间复杂度：O(E * (N + logE)) E为边的数量，N为节点数量。
  • 适用条件：但 n 很大，边 的数量 很小的时候（稀疏图），是不是可以换成从边的角度来求最短路呢？
int dijkstra_networkDelayTime2(vector<vector<int>>& times, int n, int k) {unordered_map<int, vector<pair<int, int > > > mp;for (auto a : times) {mp[a[0]].push_back({a[1], a[2]});}// 不一定要用map，使用vector效果一样：只不过是保存a[0]点指向的节点和距离vector<vector<pair<int, int>>> g(n);for (auto &t : times) {int x = t[0] - 1, y = t[1] - 1;g[x].emplace_back(y, t[2]);}作者：力扣官方题解
链接：https://leetcode.cn/problems/network-delay-time/solutions/909575/wang-luo-yan-chi-shi-jian-by-leetcode-so-6phc/
来源：力扣（LeetCode）
著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。vector<int> dismin(n + 1, INT_MAX / 2);vector<bool> visited(n + 1, false);dismin[k] = 0;// 优先队列<蓝点的最短距离，蓝点坐标>小顶堆priority_queue< pair<int, int>, vector<pair<int, int> >,  greater<>  > que;que.push({0, k});while (!que.empty()) {int minblue = que.top().second;que.pop();// 变成白点if (visited[minblue]) continue;visited[minblue] = true;// 增加这个白点会有什么影响对于 dismin// 遍历所有与新白点连接的蓝点for (pair<int, int > a : mp[minblue]) {if (!visited[a.first] && dismin[a.first] > a.second + dismin[minblue] ) {dismin[a.first] = a.second + dismin[minblue];que.push({dismin[a.first], a.first});}}}int res = *max_element(dismin.begin() + 1, dismin.end());return res == INT_MAX / 2 ? -1 : res;
}

  • 时间复杂度：O(E * (N + logE)) E为边的数量，N为节点数量

  • 空间复杂度：O(log(N^2))

  • while (!pq.empty()) 时间复杂度为 E ，while 里面 每次取元素 时间复杂度 为 logE，和 一个for循环 时间复杂度 为 N 。所以整体是 E * (N + logE)

  • sort排序与大顶堆

    • 优先队列
    • less<>表示从上到下是递减的
    • greater<>表示从上到下是递增的
    #include <bits/stdc.h>
using namespace std;// priority_queue
// less<>表示从上到下是递减的
// greater<>表示从上到下是递增的
// 默认  不加默认less<>   大顶堆就是less<> 
// 如果想要头上最小需要加上greater<>
void prio_int() {vector<int> strs = {5,8,2,6,1,8,2};priority_queue<int, vector<int>, less<>> que(strs.begin(),strs.end());while(que.empty()==0){cout<<que.top()<<endl;que.pop();}return;
}// 优先队列的自定义
// 优先队列与传统sort的相反
void prio_string() {vector<string> strs = {"xhh", "mmcy", "mi", "xhz", "abcdef"};struct cmp{bool operator()(string a,string b){return a.size()<b.size()||(a.size()==b.size() && a>b);}};priority_queue<string, vector<string>, cmp> que(strs.begin(),strs.end());while(que.empty()==0){cout<<que.top()<<endl;que.pop();}return;
}// map自动排序，unordered_map 不排序，想排序直接用
// vector<pair<int,string>>来重新装一下，再排序
void sort_map_int() {map<int, string> mp = {{1, "ab"}, {8, "zx"}, {5, "ac"}, {4, "ae"}};for (auto a : mp) {cout << a.first << "->" << a.second << endl;}return ;
}// sort pair使用 a.first   a.second
// 类型使用auto肯定是对的，但是可能没有提示first、second
void sort_pair_int() {vector<pair<int, string>> test_vector = {{5, "abc"}, {1, "ac"}, {1, "ad"}, {2, "ac"}};sort(test_vector.begin(), test_vector.end(), [](auto a, auto b) {return (a.first > b.first || (a.first == b.first && a.second > b.second));});for (auto a : test_vector ) {cout << a.first << "->" << a.second << endl;}return ;
}void sort_vector_int() {vector<int> test_vector = {5, 4, 9, 7};sort(test_vector.begin(), test_vector.end(), [](auto a, auto b) {return a > b;});for (auto a : test_vector ) {cout << a << " ";}cout << endl;return ;
}void sort_vector_vector_int() {vector<vector<int>> test_vector = {{1, 2}, {9, 8}, {1, 3}, {8, 2}, {6, 5}};sort(test_vector.begin(), test_vector.end(), [](auto a, auto b) {return (a[0] < b[0] || (a[0] == b[0] && a[1] < b[1]));});for (auto a : test_vector ) {for (auto b : a) {cout << b << " ";}cout << endl;}return ;
}int main() {sort_vector_int();cout << "****************" << endl;sort_vector_vector_int();cout << "****************" << endl;sort_pair_int();cout << "****************" << endl;sort_map_int();cout << "****************" << endl;prio_string();cout << "****************" << endl;prio_int();
}

1、743. 网络延迟时间

有 n 个网络节点，标记为 1 到 n。

给你一个列表 times，表示信号经过 有向 边的传递时间。 times[i] = (ui, vi, wi)，其中 ui 是源节点，vi 是目标节点， wi 是一个信号从源节点传递到目标节点的时间。

现在，从某个节点 K 发出一个信号。需要多久才能使所有节点都收到信号？如果不能使所有节点收到信号，返回 -1 。

示例 1：

image-20250502234548722

输入：times = [[2,1,1],[2,3,1],[3,4,1]], n = 4, k = 2
输出：2

示例 2：

输入：times = [[1,2,1]], n = 2, k = 1
输出：1

示例 3：

输入：times = [[1,2,1]], n = 2, k = 2
输出：-1

提示：

  • 1 <= k <= n <= 100
  • 1 <= times.length <= 6000
  • times[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 0 <= wi <= 100
  • 所有 (ui, vi) 对都 互不相同（即，不含重复边）
/*普通版本
*/class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {vector<int> dp(n + 1, INT_MAX / 2);dp[k] = 0;vector<vector<int>> dis(n + 1, vector<int>(n + 1, INT_MAX / 2));for (auto& a : times) {dis[a[0]][a[1]] = a[2];}vector<int> visited(n + 1, false);//for(int i = 0;i<=n;i++){while(1) {int blue = 0;for (int i = 0; i <= n; i++) {if (!visited[i] && dp[blue] > dp[i]) {blue = i;}}// 再次遇到说明最小值就是0了，结束了if(visited[blue]) break;visited[blue] = true;for (int i = 0; i <= n; i++) {if (dp[i] > dp[blue] + dis[blue][i]) {dp[i] = dp[blue] + dis[blue][i];}}}int res = *max_element(dp.begin() + 1, dp.end());return res == INT_MAX / 2 ? -1 : res;}
};// 堆优化版本
class Solution {
public:int networkDelayTime(vector<vector<int>>& times, int n, int k) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> que;//	que.push({k,0});que.push({0, k});vector<bool> visited(n + 1, false);vector<int> dp(n + 1, INT_MAX / 2);dp[k] = 0;while (!que.empty()) {auto blue = que.top();que.pop();// 这里不用想那么多：看见置true直接在前面加判断if( visited[blue.second]) continue;visited[blue.second] = true;for (auto& a : times) {// 这里直接取头节点不是这个blue的直接跳过，已经为白的直接跳过// 目的是为了取最小的蓝if (a[0] != blue.second || visited[a[1]] )continue;if (dp[a[1]] > dp[blue.second] + a[2]) {dp[a[1]] = dp[blue.second] + a[2];que.push({dp[a[1]], a[1]});}}}int res = *max_element(dp.begin() + 1, dp.end());return res == INT_MAX / 2 ? -1 : res;}
};

2、1334. 阈值距离内邻居最少的城市

  • 直接使用堆优化：注意双向图即可

有 n 个城市，按从 0 到 n-1 编号。给你一个边数组 edges，其中 edges[i] = [fromi, toi, weighti] 代表 fromi 和 toi 两个城市之间的双向加权边，距离阈值是一个整数 distanceThreshold。

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

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

示例 1：

image-20250502234526613

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

image-20250502234509711

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

/*无向图的堆优化djikstra算法：
*/
class Solution {
public:int target(int n, vector<vector<int>>& edges, int distanceThreshold,int k) {priority_queue<pair<int, int>, vector<pair<int, int>>, greater<>> que;que.push({0, k});vector<int> dis(n, INT_MAX / 2);dis[k] = 0;vector<bool> visited(n, false);while (!que.empty()) {int blue = que.top().second;que.pop();if (visited[blue])continue;visited[blue] = true;for (auto& a : edges) {if (a[0]==blue && dis[a[1]] > dis[a[0]] + a[2]) {dis[a[1]] = dis[a[0]] + a[2];que.push({dis[a[1]], a[1]});}if (a[1]==blue && dis[a[0]] > dis[a[1]] + a[2]) {dis[a[0]] = dis[a[1]] + a[2];que.push({dis[a[0]], a[0]});}}}int res = 0;for (auto& a : dis) {if (a <= distanceThreshold)res++;}return res;}int findTheCity(int n, vector<vector<int>>& edges, int distanceThreshold) {int res = INT_MAX / 2;int resdex = 0;for (int i = 0; i < n; i++) {int mid = target(n, edges, distanceThreshold, i);if (mid <= res) {res = mid;resdex = i;}}return  resdex;}
};

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

如若内容造成侵权/违法违规/事实不符，请联系长河编程网进行投诉反馈email:809451989@qq.com，一经查实，立即删除！

相关文章

uniapp-商城-43-shop 后台管理 页面

uniapp-商城-43-shop 后台管理 页面

后台管理较为简单&#xff0c;主要用于后台数据的管理&#xff0c;包含商品类别和商品信息&#xff0c;其实还可以扩展到管理用户等等 1、后台首页 包含 分类管理 商品管理 关于商家等几个栏目 主要代码&#xff1a; <template><view class"manage">…
阅读更多...
LeetCode 1. 两数之和（Java）

LeetCode 1. 两数之和（Java）

LeetCode 1. 两数之和&#xff08;暴力 vs 哈希表&#xff09; 题目描述 给定一个整数数组 nums 和一个整数 target&#xff0c;要求找出数组中和为目标值的两个数&#xff0c;并返回它们的下标。假设每个输入只有一种答案&#xff0c;且同一元素不能重复使用。 示例&#xf…
阅读更多...
《软件项目管理》笔记一

《软件项目管理》笔记一

软件项目管理概述 项目管理属于软件工程的组成之一&#xff0c;另外两部分为&#xff1a;软件开发&#xff0c;过程改进。 参考书如下&#xff1a; 1.1 项目与软件项目 1、项目&#xff1a; 为了创造一个唯一的产品或提供一个唯一的服务而进行 的临时性的努力。 2、项目的…
阅读更多...
深度学习：智能车牌识别系统（python）

深度学习：智能车牌识别系统（python）

这是一个基于opencv的智能车牌识别系统，有GUI界面。程序能自动识别图片中的车牌号码，并支持中文和英文字符识别，支持选择本地图片文件，支持多种图片格式（jpg、jpeg、png、bmp、gif）。 下面，我将按模块功能对代码进行分段说明： 1. 导入模块部分 import tkinter as tk…
阅读更多...
Redis 持久化机制全面解析：RDB 与 AOF 的原理与实践

Redis 持久化机制全面解析：RDB 与 AOF 的原理与实践

目录 前言1. Redis 持久化的总体思路2. RDB&#xff1a;快照机制详解2.1 RDB 的工作原理2.2 RDB 的优势2.3 RDB 的局限性 3. AOF&#xff1a;追加日志机制详解3.1 AOF 的工作原理3.2 AOF 的优势3.3 AOF 的缺陷 4. RDB 与 AOF 的对比分析4.1 数据丢失风险4.2 文件大小与恢复速度…
阅读更多...
混淆矩阵（Confusion Matrix）

混淆矩阵（Confusion Matrix）

混淆矩阵&#xff08;Confusion Matrix&#xff09;是一个用于评估分类模型性能的工具&#xff0c;特别是在机器学习和统计学领域。它展示了模型预测结果与实际结果之间的关系。混淆矩阵通常用于二分类或多分类问题中&#xff0c;但也可以扩展到更多类别的情况。 一、混淆矩阵…
阅读更多...
TB6600HG是一款PWM（脉宽调制）斩波型单芯片双极性正弦波微步进电机驱动集成电路。

TB6600HG是一款PWM（脉宽调制）斩波型单芯片双极性正弦波微步进电机驱动集成电路。

该驱动器支持电机的正向和反向旋转控制&#xff0c;并具有多种激励模式&#xff0c;包括2相、1-2相、W1-2相、2W1-2相和4W1-2相。 使用这款驱动器&#xff0c;只需时钟信号即可驱动2相双极性步进电机&#xff0c;且振动小、效率高。 主要特点&#xff1a; 单芯片双极性正弦波…
阅读更多...
【论文阅读】Towards Stable Backdoor Purification through Feature Shift Tuning

【论文阅读】Towards Stable Backdoor Purification through Feature Shift Tuning

NeurIPS 2023 & 2024 Spotlight https://github.com/AISafety-HKUST/Backdoor_Safety_Tuning 我们的贡献包括&#xff1a; 我们对各种调整策略进行了广泛的评估&#xff0c;发现普通的微调&#xff08;FT&#xff09;和简单的线性探测&#xff08;LP&#xff09;在高投毒率…
阅读更多...
创龙全志T536全国产（4核A55 ARM+RISC-V+NPU 17路UART）工业开发板硬件说明书

创龙全志T536全国产（4核A55 ARM+RISC-V+NPU 17路UART）工业开发板硬件说明书

前 言 本文档主要介绍TLT536-EVM评估板硬件接口资源以及设计注意事项等内容。 T536MX-CXX/T536MX-CEN2处理器的IO电平标准一般为1.8V、3.3V，上拉电源一般不超过3.3V或1.8V，当外接信号电平与IO电平不匹配时，中间需增加电平转换芯片或信号隔离芯片。按键或接口需考虑ESD设计…
阅读更多...
Jenkins忘记admin密码后的恢复步骤

Jenkins忘记admin密码后的恢复步骤

提示&#xff1a;文章写完后&#xff0c;目录可以自动生成&#xff0c;如何生成可参考右边的帮助文档 文章目录 前言一、pandas是什么&#xff1f;二、使用步骤 1.引入库2.读入数据 总结 前言 提示&#xff1a;这里可以添加本文要记录的大概内容&#xff1a; 时间较长没有使用…
阅读更多...
React 组件prop添加类型

React 组件prop添加类型

给函数的props做注解 import { useState } from reacttype Props { className:string,title?:string } // 自定义一个Button组件 function Button(props:Props){// 解构出classname\const {className} propsreturn <button className{className}>点击我</button&g…
阅读更多...
如何使用docker配置ros-noetic环境并使用rviz，gazebo

如何使用docker配置ros-noetic环境并使用rviz，gazebo

参考链接&#xff1a;【Ubuntu】Docker中配置ROS并可视化Rviz及Gazebo_docker ros-CSDN博客 前言&#xff1a; 其实这个东西是相当必要的&#xff0c;因为我们有时候需要在一台电脑上跑好几个项目&#xff0c;每个项目都有不同的依赖&#xff0c;这些依赖冲突搞得人头皮发麻&…
阅读更多...
（已完结）完美解决C盘拓展卷是灰色的无法扩容的问题以及如何正确地在WINDOS上从一个盘扩容到C盘

（已完结）完美解决C盘拓展卷是灰色的无法扩容的问题以及如何正确地在WINDOS上从一个盘扩容到C盘

众所周知&#xff0c;window系统在“计算机”管理中自带了一个磁盘管理系统 但是在使用过程中会出现各种各样无法扩容的毛病。 第一&#xff1a;首先排查&#xff0c;大多数人在扩容之前忽视了一点就是&#xff0c;我们现代的很多新机器都是默认开启BitLocker加密的&#xff…
阅读更多...
阿里云服务器-centos部署定时同步数据库数据-dbswitch

阿里云服务器-centos部署定时同步数据库数据-dbswitch

前言&#xff1a; 本文章介绍通过dbswitch工具实现2个mysql数据库之间实现自动同步数据。 应用场景&#xff1a;公司要求实现正式环境数据库数据自动冷备 dbswitch依赖环境&#xff1a;git ,maven,jdk 方式一&#xff1a; 不需要在服务器中安装git和maven&#xff0c;直接用…
阅读更多...
leetcode 141. Linked List Cycle

leetcode 141. Linked List Cycle

题目描述&#xff1a; 代码&#xff1a; 用哈希表也可以解决&#xff0c;但真正考察的是用快慢指针法。 /*** Definition for singly-linked list.* struct ListNode {* int val;* ListNode *next;* ListNode(int x) : val(x), next(NULL) {}* };*/ class Soluti…
阅读更多...
微软输入法常用快捷键介绍以及调教技巧

微软输入法常用快捷键介绍以及调教技巧

微软输入法&#xff08;Microsoft Pinyin Input Method&#xff09;是 Windows 系统内置的中文输入工具&#xff0c;以其高效、智能化的特点广受用户喜爱。掌握其常用快捷键和特殊模式可以显著提升输入效率。本文将介绍微软输入法在 Windows 10/11 环境下的常用快捷键及 U 模式…
阅读更多...
Paddle Serving|部署一个自己的OCR识别服务器

Paddle Serving|部署一个自己的OCR识别服务器

前言 之前使用C部署了自己的OCR识别服务器&#xff0c;Socket网络传输部分是自己写的&#xff0c;回过头来一看&#xff0c;自己犯傻了&#xff0c;PaddleOCR本来就有自己的OCR服务器项目&#xff0c;叫PaddleServing&#xff0c;这里记录一下部署过程。 1 下载依赖环境 1.1 …
阅读更多...
AI与情感计算：如何让机器更好地理解人类情感与情绪？

AI与情感计算：如何让机器更好地理解人类情感与情绪？

引言&#xff1a;当AI遇上人类情感 当我们说起人工智能&#xff0c;脑海里第一时间想到的&#xff0c;可能是聪明的语音助手、精准的推荐系统&#xff0c;或者无所不能的机器人。但如果有一天&#xff0c;这些机器不再只是“执行指令”&#xff0c;而是能看出你今天心情不好&am…
阅读更多...
普通IT的股票交易成长史--20250507晚复盘

普通IT的股票交易成长史--20250507晚复盘

声明&#xff1a;本文章的内容只是自己学习的总结&#xff0c;不构成投资建议。价格行为理论学习可参考简介中的几位&#xff0c;感谢他们的无私奉献。 送给自己的话&#xff1a; 仓位就是生命&#xff0c;绝对不能满仓&#xff01;&#xff01;&#xff01;&#xff01;&…
阅读更多...
加速项目落地（Trae编辑器）

加速项目落地（Trae编辑器）

目录 vscode安装python支持 vscode常用插件 Trae编辑器 两个界面合成 补充&#xff08;QT开发的繁琐&#xff09; AI编程哪家强&#xff1f;Cursor、Trae深度对比&#xff0c;超详细&#xff01; - 知乎 Trae兼容vscode的插件&#xff0c;我们可以先在vscode里面装好再一…
阅读更多...
最新文章
推荐文章

Copyright @ 2022~2023