2023-8-30 Dijkstra 求最短路(一)

题目链接:Dijkstra求最短路 I
在这里插入图片描述

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 510;int n, m;
int g[N][N];
int dist[N];
bool st[N];int dijkstra()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;for(int i = 0; i < n; i++){// t 代表没有确认的最短路长度的最小值int t = -1;for(int j = 1; j <= n; j ++){if(!st[j] && (t == -1 || dist[t] > dist[j])){t = j;}}st[t] = true;// 更新其他点的距离for(int j = 1; j <= n; j++){dist[j]  = min(dist[j], dist[t] + g[t][j]);}}if(dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}int main()
{cin >> n >> m;memset(g, 0x3f, sizeof g);for(int i = 0; i < m; i++){int a, b, c;cin >> a >> b >> c;g[a][b] = min(g[a][b], c);}cout << dijkstra() << endl;return 0;
}

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

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

相关文章

Leetcode每日一题:1448. 统计二叉树中好节点的数目

原题 给你一棵根为 root 的二叉树&#xff0c;请你返回二叉树中好节点的数目。 「好节点」X 定义为&#xff1a;从根到该节点 X 所经过的节点中&#xff0c;没有任何节点的值大于 X 的值。 示例 1&#xff1a; 输入&#xff1a;root [3,1,4,3,null,1,5] 输出&#xff1a;4 解…

C语言网络编程:实现自己的高性能网络框架

一般生产环境中最耗时的其实是业务逻辑处理。所以&#xff0c;是不是可以将处理业务逻辑的代码给拆出来丢到线程池中去执行。 比如像下面这样&#xff1a; ​我们事先创建好一堆worker线程&#xff0c;主线程accepter拿到一个连接上来的套接字&#xff0c;就从线程池中取出一个…

开始MySQL之路——MySQL的DataGrip图形化界面

下载DataGrip 下载地址&#xff1a;Download DataGrip: Cross-Platform IDE for Databases & SQL 安装DataGrip 准备好一个文件夹&#xff0c;不要中文和空格 C:\Develop\DataGrip 激活DataGrip 激活码&#xff1a; VPQ9LWBJ0Z-eyJsaWNlbnNlSWQiOiJWUFE5TFdCSjBaIiwibGl…

python+django+mysql旅游景点推荐系统-前后端分离(源码+文档)

系统主要采用Python开发技术和MySQL数据库开发技术以及基于OpenCV的图像识别。系统主要包括系统首页、个人中心、用户管理、景点信息管理、景点类型管理、景点门票管理、在线反馈、系统管理等功能&#xff0c;从而实现智能化的旅游景点推荐方式&#xff0c;提高旅游景点推荐的效…

MinIO框架安装使用+实现上传需求

MinIO框架 什么是MinIO框架如何安装&#xff08;Docker版&#xff09;安装步骤1. 查询MinIO的服务版本2. 拉取MinIO3.启动报错在docker中没有操作文件的权限 4. 访问 简单配置1.找到创建用户界面2. 设置用户信息3. 创建一个桶 使用MinIO依赖搭建MinIO的初始化API存储桶的基本操…

SaaS多租户系统架构设计

前言&#xff1a;多租户是SaaS&#xff08;Software-as-a-Service&#xff09;下的一个概念&#xff0c;意思为软件即服务&#xff0c;即通过网络提供软件服务。SaaS平台供应商将应用软件统一部署在自己的服务器上&#xff0c;客户可以根据工作的实际需求&#xff0c;通过互联网…

二级MySQL(十)——单表查询

这里我们只在一个表内查询&#xff0c;用到的是较为简单的SELECT函数形式 1、查询指定的字段&#xff1a; 用到的数据库是之前提到的S、P、SP数据库 S表格用到的总数据&#xff1a; 首先我们查询所有供应商的序号和名字 这时都是独立的&#xff0c;没有关系&#xff0c;我们找…

Acwing796.子矩阵的和

理解二维前缀和&#xff1a; #include <iostream>using namespace std;const int N 1010;int a[N][N], s[N][N];int main() {int n, m, q;cin >> n >> m >> q;for (int i 1; i < n; i)for (int j 1; j < m; j) {scanf("%d", &a…

SpringBoot的自动装配源码分析

文章目录 一&#xff1a;什么是自动装配二、springboot的启动流程1.调用SpringApplication&#xff08;&#xff09;的构造方法2.执行核心run方法&#xff08;&#xff09;3.执行核心prepareContext&#xff08;&#xff09;4.执行核心refreshContext&#xff08;&#xff09;5…

机房安全之道:构筑坚固的网络防线

引言&#xff1a; 在数字化时代&#xff0c;机房成为了许多组织和企业的核心基础设施&#xff0c;承载着重要的数据和应用。然而&#xff0c;随着网络攻击日益猖獗&#xff0c;机房的安全性显得尤为重要。本文将深入探讨如何构建坚固的网络防线&#xff0c;保护机房免受攻击的方…

测试理论与方法----测试流程的第四个步骤:执行测试,提出缺陷

8、执行测试—–>提交缺陷报告 测试流程&#xff1a;执行测试—–>提交缺陷报告 1、缺陷的概述&#xff08;回顾&#xff09; 结果角度&#xff1a;实际结果和预期结果不一致 需求角度&#xff1a;所有不满足需求或超出需求的&#xff0c;都是缺陷 2、缺陷的相关属性…

基于React实现无限滚动的日历详细教程,附源码【手写日历教程第二篇】

前言 最常见的日历大部分都是滚动去加载更多的月份&#xff0c;而不是让用户手动点击按钮切换日历月份。滚动加载的交互方式对于用户而言是更加丝滑和舒适的&#xff0c;没有明显的操作割裂感。 那么现在需要做一个这样的无限滚动的日历&#xff0c;前端开发者应该如何去思考…

设计模式--代理模式(Proxy Pattern)

一、什么是代理模式&#xff08;Proxy Pattern&#xff09; 代理模式&#xff08;Proxy Pattern&#xff09;是一种结构型设计模式&#xff0c;它允许一个对象&#xff08;代理&#xff09;充当另一个对象&#xff08;真实对象&#xff09;的接口&#xff0c;以控制对该对象的…

requests之post请求data传参和json传参区别

问题描述 在一次接口post测试请求传参异常的记录 print(header)rp requests.post(EvnUrlConfig.getUrl(url),headersheader,datauserDevcieParam)传输到后台服务器报了异常 原因分析&#xff1a; 显而易见我的请求头的content-type类型有异常了&#xff0c;但我明明传的是app…

如何利用人工智能实现软件测试的左移

在本文中&#xff0c;我们&#xff08;作者&#xff09;探讨了如何利用人工智能的力量&#xff0c;在软件测试领域实现左移。 用AI驱动的创新变革测试领域 测试在确保应用程序质量和可靠性方面发挥着至关重要的作用。然而&#xff0c;随着测试要求变得越来越复杂&#xff0c;人…

2023年最新版Windows环境下|Java8(jdk1.8)安装教程

个人主页&#xff1a;平行线也会相交 欢迎 点赞&#x1f44d; 收藏✨ 留言✉ 加关注&#x1f493;本文由 平行线也会相交 原创 收录于专栏【JavaSE_primary】 jdk1.8的下载和使用总共分为3个步骤&#xff1a; jdk1.8的下载、jdk1.8的安装、配置环境变量。 目录 一、jdk1.8下载…

C#,《小白学程序》第五课:队列(Queue)

日常生活中常见的排队&#xff0c;软件怎么体现呢&#xff1f; 排队的基本原则是&#xff1a;先到先得&#xff0c;先到先吃&#xff0c;先进先出 1 文本格式 /// <summary> /// 《小白学程序》第五课&#xff1a;队列&#xff08;Queue&#xff09; /// 日常生活中常见…

39、springboot的前端静态资源的WebJar支持(bootstrap、jquery等)及自定义图标和首页

★ WebJar支持 Spring Boot支持加载WebJar包中的静态资源&#xff08;图片、JS、CSS&#xff09;&#xff0c; WebJar包中的静态资源都会映射到/webjars/**路径。——这种方式下&#xff0c;完全不需要将静态资源复制到应用的静态资源目录下。只要添加webjar即可。假如在应用的…

【LeetCode-中等题】2. 两数相加

文章目录 题目方法一&#xff1a;借助一个进制位&#xff0c;以及更新尾结点方法一改进&#xff1a;相比较第一种&#xff0c;给head一个临时头节点&#xff08;开始节点&#xff09;&#xff0c;最后返回的时候返回head.next&#xff0c;这样可以省去第一次的判断 题目 方法一…

北大C++课后记录:自增、自减运算符重载的小Demo

前言 自增、自减运算符有前置&#xff08;x&#xff09;和后置&#xff08;x&#xff09;之分&#xff0c;为了对其进行区分&#xff0c;C规定&#xff1a; 前置运算符作为一元运算符进行重载&#xff1a;&#xff08;注意T1对象和T2对象是有差异的&#xff09; 后置运算符作…