算法训练营|图论第10天 Bellman_ford:优化算法,判断负权算法,单源有限最短路

本文主要是介绍算法训练营|图论第10天 Bellman_ford:优化算法,判断负权算法,单源有限最短路,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目:Bellman_ford:优化算法

题目链接:

94. 城市间货物运输 I (kamacoder.com)

代码:

#include<bits/stdc++.h>
using namespace std;
struct Edge {int to;int val;Edge(int t, int w) :to(t), val(w) {}
};
int main() {int n, m;cin >> n >> m;int p1, p2, val;vector<list<Edge>>grid(n + 1);for (int i = 0; i < m; i++) {cin >> p1 >> p2 >> val;grid[p1].push_back(Edge(p2, val));}int start = 1;int end = n;queue<int>que;vector<bool>InQueue(n + 1, false);vector<int>minDist(n + 1, INT_MAX);minDist[start] = 0;que.push(start);while (!que.empty()) {int cur = que.front();que.pop();InQueue[cur] = false;for (Edge edge : grid[cur]) {int from = cur;int to = edge.to;int val = edge.val;if (minDist[to] > minDist[from] + val) {minDist[to] = minDist[from] + val;if (InQueue[to] == false) {que.push(to);InQueue[to] = true;}}}}if (minDist[end] == INT_MAX) cout << "unconnected" << endl;else cout << minDist[end] << endl;
}

题目:判断负权算法

题目链接:

95. 城市间货物运输 II (kamacoder.com)

代码:

#include<bits/stdc++.h>
using namespace std;
struct Edge {int to;int val;Edge(int t, int w) :to(t), val(w) {}
};
int main() {int n, m;cin >> n >> m;int p1, p2, val;vector<vector<int>>grid;for (int i = 0; i < m; i++) {cin >> p1 >> p2 >> val;grid.push_back({ p1,p2,val });}int start = 1;int end = n;vector<int>minDist(n + 1, INT_MAX);minDist[start] = 0;bool flag = false;for (int i = 1; i <= n ; i++) {for (vector<int>vec : grid) {int from = vec[0];int to = vec[1];int val = vec[2];if (i < n) {if (minDist[from] != INT_MAX && minDist[from] + val < minDist[to]) {minDist[to] = minDist[from] + val;}}else {if (minDist[from] != INT_MAX && minDist[from] + val < minDist[to]) {flag = true;}}}}if (flag) {cout << "circle" << endl;}else if (minDist[end] == INT_MAX) {cout << "unconnected" << endl;}else {cout << minDist[end] << endl;}
}

题目:单源有限最短路

题目链接:

96. 城市间货物运输 III (kamacoder.com)

代码:

#include<bits/stdc++.h>
using namespace std;
struct Edge {int to;int val;Edge(int t, int w) :to(t), val(w) {}
};
int main() {int n, m;cin >> n >> m;int p1, p2, val;vector<vector<int>>grid;for (int i = 0; i < m; i++) {cin >> p1 >> p2 >> val;grid.push_back({ p1,p2,val });}int src, dst, k;cin >> src >> dst >> k;vector<int> minDist(n + 1, INT_MAX);minDist[src] = 0;vector<int> minDist_copy(n + 1); // 用来记录上一次遍历的结果for (int i = 1; i <= k + 1; i++) {minDist_copy = minDist;for (vector<int> &vec : grid) {int from = vec[0];int to = vec[1];int val = vec[2];if (minDist_copy[from] != INT_MAX && minDist[to] > minDist_copy[from] + val) {minDist[to] = minDist_copy[from] + val;}}}if (minDist[dst] == INT_MAX) cout << "unreachable" << endl; // 不能到达终点else cout << minDist[dst] << endl; // 到达终点最短路径
}

这篇关于算法训练营|图论第10天 Bellman_ford:优化算法,判断负权算法,单源有限最短路的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1131409

相关文章

Java中的雪花算法Snowflake解析与实践技巧

《Java中的雪花算法Snowflake解析与实践技巧》本文解析了雪花算法的原理、Java实现及生产实践,涵盖ID结构、位运算技巧、时钟回拨处理、WorkerId分配等关键点,并探讨了百度UidGen... 目录一、雪花算法核心原理1.1 算法起源1.2 ID结构详解1.3 核心特性二、Java实现解析2.

Go语言中nil判断的注意事项(最新推荐)

《Go语言中nil判断的注意事项(最新推荐)》本文给大家介绍Go语言中nil判断的注意事项,本文给大家介绍的非常详细,对大家的学习或工作具有一定的参考借鉴价值,需要的朋友参考下吧... 目录1.接口变量的特殊行为2.nil的合法类型3.nil值的实用行为4.自定义类型与nil5.反射判断nil6.函数返回的

MyBatisPlus如何优化千万级数据的CRUD

《MyBatisPlus如何优化千万级数据的CRUD》最近负责的一个项目,数据库表量级破千万,每次执行CRUD都像走钢丝,稍有不慎就引起数据库报警,本文就结合这个项目的实战经验,聊聊MyBatisPl... 目录背景一、MyBATis Plus 简介二、千万级数据的挑战三、优化 CRUD 的关键策略1. 查

python判断文件是否存在常用的几种方式

《python判断文件是否存在常用的几种方式》在Python中我们在读写文件之前,首先要做的事情就是判断文件是否存在,否则很容易发生错误的情况,:本文主要介绍python判断文件是否存在常用的几种... 目录1. 使用 os.path.exists()2. 使用 os.path.isfile()3. 使用

Go语言如何判断两张图片的相似度

《Go语言如何判断两张图片的相似度》这篇文章主要为大家详细介绍了Go语言如何中实现判断两张图片的相似度的两种方法,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 在介绍技术细节前,我们先来看看图片对比在哪些场景下可以用得到:图片去重:自动删除重复图片,为存储空间"瘦身"。想象你是一个

Python如何判断字符串中是否包含特殊字符并替换

《Python如何判断字符串中是否包含特殊字符并替换》这篇文章主要为大家详细介绍了如何使用Python实现判断字符串中是否包含特殊字符并使用空字符串替换掉,文中的示例代码讲解详细,感兴趣的小伙伴可以了... 目录python判断字符串中是否包含特殊字符方法一:使用正则表达式方法二:手动检查特定字符Pytho

SpringBoot中HTTP连接池的配置与优化

《SpringBoot中HTTP连接池的配置与优化》这篇文章主要为大家详细介绍了SpringBoot中HTTP连接池的配置与优化的相关知识,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一... 目录一、HTTP连接池的核心价值二、Spring Boot集成方案方案1:Apache HttpCl

使用雪花算法产生id导致前端精度缺失问题解决方案

《使用雪花算法产生id导致前端精度缺失问题解决方案》雪花算法由Twitter提出,设计目的是生成唯一的、递增的ID,下面:本文主要介绍使用雪花算法产生id导致前端精度缺失问题的解决方案,文中通过代... 目录一、问题根源二、解决方案1. 全局配置Jackson序列化规则2. 实体类必须使用Long封装类3.

PyTorch高级特性与性能优化方式

《PyTorch高级特性与性能优化方式》:本文主要介绍PyTorch高级特性与性能优化方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录一、自动化机制1.自动微分机制2.动态计算图二、性能优化1.内存管理2.GPU加速3.多GPU训练三、分布式训练1.分布式数据

MySQL中like模糊查询的优化方案

《MySQL中like模糊查询的优化方案》在MySQL中,like模糊查询是一种常用的查询方式,但在某些情况下可能会导致性能问题,本文将介绍八种优化MySQL中like模糊查询的方法,需要的朋友可以参... 目录1. 避免以通配符开头的查询2. 使用全文索引(Full-text Index)3. 使用前缀索