算法训练营|图论第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

相关文章

Python如何使用__slots__实现节省内存和性能优化

《Python如何使用__slots__实现节省内存和性能优化》你有想过,一个小小的__slots__能让你的Python类内存消耗直接减半吗,没错,今天咱们要聊的就是这个让人眼前一亮的技巧,感兴趣的... 目录背景:内存吃得满满的类__slots__:你的内存管理小助手举个大概的例子:看看效果如何?1.

一文详解SpringBoot响应压缩功能的配置与优化

《一文详解SpringBoot响应压缩功能的配置与优化》SpringBoot的响应压缩功能基于智能协商机制,需同时满足很多条件,本文主要为大家详细介绍了SpringBoot响应压缩功能的配置与优化,需... 目录一、核心工作机制1.1 自动协商触发条件1.2 压缩处理流程二、配置方案详解2.1 基础YAML

SpringBoot实现MD5加盐算法的示例代码

《SpringBoot实现MD5加盐算法的示例代码》加盐算法是一种用于增强密码安全性的技术,本文主要介绍了SpringBoot实现MD5加盐算法的示例代码,文中通过示例代码介绍的非常详细,对大家的学习... 目录一、什么是加盐算法二、如何实现加盐算法2.1 加盐算法代码实现2.2 注册页面中进行密码加盐2.

Java时间轮调度算法的代码实现

《Java时间轮调度算法的代码实现》时间轮是一种高效的定时调度算法,主要用于管理延时任务或周期性任务,它通过一个环形数组(时间轮)和指针来实现,将大量定时任务分摊到固定的时间槽中,极大地降低了时间复杂... 目录1、简述2、时间轮的原理3. 时间轮的实现步骤3.1 定义时间槽3.2 定义时间轮3.3 使用时

MySQL中慢SQL优化的不同方式介绍

《MySQL中慢SQL优化的不同方式介绍》慢SQL的优化,主要从两个方面考虑,SQL语句本身的优化,以及数据库设计的优化,下面小编就来给大家介绍一下有哪些方式可以优化慢SQL吧... 目录避免不必要的列分页优化索引优化JOIN 的优化排序优化UNION 优化慢 SQL 的优化,主要从两个方面考虑,SQL 语

MySQL中慢SQL优化方法的完整指南

《MySQL中慢SQL优化方法的完整指南》当数据库响应时间超过500ms时,系统将面临三大灾难链式反应,所以本文将为大家介绍一下MySQL中慢SQL优化的常用方法,有需要的小伙伴可以了解下... 目录一、慢SQL的致命影响二、精准定位问题SQL1. 启用慢查询日志2. 诊断黄金三件套三、六大核心优化方案方案

Redis中高并发读写性能的深度解析与优化

《Redis中高并发读写性能的深度解析与优化》Redis作为一款高性能的内存数据库,广泛应用于缓存、消息队列、实时统计等场景,本文将深入探讨Redis的读写并发能力,感兴趣的小伙伴可以了解下... 目录引言一、Redis 并发能力概述1.1 Redis 的读写性能1.2 影响 Redis 并发能力的因素二、

使用国内镜像源优化pip install下载的方法步骤

《使用国内镜像源优化pipinstall下载的方法步骤》在Python开发中,pip是一个不可或缺的工具,用于安装和管理Python包,然而,由于默认的PyPI服务器位于国外,国内用户在安装依赖时可... 目录引言1. 为什么需要国内镜像源?2. 常用的国内镜像源3. 临时使用国内镜像源4. 永久配置国内镜

C#原型模式之如何通过克隆对象来优化创建过程

《C#原型模式之如何通过克隆对象来优化创建过程》原型模式是一种创建型设计模式,通过克隆现有对象来创建新对象,避免重复的创建成本和复杂的初始化过程,它适用于对象创建过程复杂、需要大量相似对象或避免重复初... 目录什么是原型模式?原型模式的工作原理C#中如何实现原型模式?1. 定义原型接口2. 实现原型接口3

如何通过Golang的container/list实现LRU缓存算法

《如何通过Golang的container/list实现LRU缓存算法》文章介绍了Go语言中container/list包实现的双向链表,并探讨了如何使用链表实现LRU缓存,LRU缓存通过维护一个双向... 目录力扣:146. LRU 缓存主要结构 List 和 Element常用方法1. 初始化链表2.