当前位置: 首页 > news >正文

最短路:spfa算法

最短路:spfa算法

    • 题目描述
    • 参考代码![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/3be484da34a84911a0a7dab3f1d84945.png)

题目描述

参考代码在这里插入图片描述

输入示例

3 3
1 2 5
2 3 -3
1 3 4

输出示例

2
#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>using namespace std;const int N = 1e5 + 10;int n, m;
int h[N], e[N], ne[N], w[N], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b; ne[idx] = h[a]; w[idx] = c; h[a] = idx; idx++;
}int spfa()
{memset(dist, 0x3f, sizeof dist);dist[1] = 0;queue<int> q;q.push(1);st[1] = true;while (q.size()){auto t = q.front();q.pop();st[t] = false;for (int i = h[t]; i != -1; i = ne[i]){int j = e[i];if (dist[j] > dist[t] + w[i]){dist[j] = dist[t] + w[i];if (!st[j]){q.push(j);st[j] = true;}}}}if (dist[n] == 0x3f3f3f3f) return -1;return dist[n];
}int main()
{scanf("%d%d", &n, &m);memset(h, -1, sizeof h);while (m -- ){int x, y, z;scanf("%d%d%d", &x, &y, &z);add(x, y, z);}int t = spfa();if (t == -1) printf("impossible\n");else printf("%d\n", t);return 0;
}

相关文章:

最短路:spfa算法

最短路&#xff1a;spfa算法 题目描述参考代码![在这里插入图片描述](https://img-blog.csdnimg.cn/direct/3be484da34a84911a0a7dab3f1d84945.png) 题目描述 参考代码 输入示例 3 3 1 2 5 2 3 -3 1 3 4输出示例 2#include <iostream> #include <cstring> #inc…...

算法笔记 图论和优先级队列的笔记

图论 DFS stack O(h) 不具有最短性 BFS queue O(2^h) 最短路 迪杰斯特拉算法 初始化&#xff1a; 将起始节点 A 的距离设为 0。将其他所有节点的距离设为无穷大。创建一个优先队列&#xff0c;并将起始节点 A 加入优先队列。 处理队列&#xff1a; …...

6.每日LeetCode-数组类,找到所有数组中消失的数字

题目 448找到所有数组中消失的数字.go 给你一个含 n 个整数的数组 nums &#xff0c;其中 nums[i] 在区间 [1, n] 内。请你找出所有在 [1, n] 范围内但没有出现在 nums 中的数字&#xff0c;并以数组的形式返回结果。 示例 1&#xff1a; 输入&#xff1a;nums [4,3,2,7,8,2,…...

【Three.js】知识梳理十:Three.js纹理贴图

1. 纹理贴图 在Three.js中&#xff0c;纹理贴图是一种将二维图像贴到三维物体表面的技术&#xff0c;以增强物体的视觉表现。纹理贴图可以使物体表面更加真实、细腻&#xff0c;为场景增色不少。 在Three.js中&#xff0c;纹理贴图的加载主要通过THREE.TextureLoader类实现。…...

mysql order by后跟case when

在SQL中&#xff0c;ORDER BY子句用于对查询结果进行排序。当在ORDER BY后面使用CASE语句时&#xff0c;它的原理是&#xff1a;根据CASE语句中定义的条件和结果&#xff0c;为查询结果集中的每一行生成一个临时的排序值。然后&#xff0c;根据这些排序值对结果集进行排序。 具…...

数字孪生赋能的智慧园区物联网云平台建设方案(97页PPT)

方案介绍&#xff1a; 本方案通过数字孪生技术赋能智慧园区物联网云平台&#xff0c;实现了园区的智能化管理、优化资源配置、提高运营效率等目标。同时提升园区的安全性、环保性和可持续性。最后&#xff0c;该方案还充分考虑了系统的可扩展性、安全性和可靠性&#xff0c;为…...

TikTok小店运营策略

TikTok&#xff0c;作为一款全球知名的短视频社交平台&#xff0c;其用户基数庞大且日活跃用户持续增长&#xff0c;为商家提供了巨大的商机。欧洲作为TikTok的重要市场之一&#xff0c;其小店功能为商家提供了一个展示和销售产品的新渠道。本文将探讨如何有效地运营TikTok小店…...

Docker面试整理-如何查看和管理Docker容器的日志?

管理和查看 Docker 容器的日志是 Docker 容器管理的重要部分,有助于监控应用的行为和诊断问题。Docker 提供了几种方法来查看和管理容器日志。 查看容器日志 要查看 Docker 容器的日志,你可以使用 docker logs 命令。这个命令会打印容器的 STDOUT 和 STDERR 输出,这是大多数…...

Java从放弃到继续放弃

并发编程 为什么需要多线程&#xff1f; 由于硬件的发展&#xff0c;CPU的核数增多&#xff0c;如果仍然使用单线程对CPU资源会造成浪费。同时&#xff0c;单线程也会出现阻塞的问题。所以&#xff0c;选择向多线程转变。 多线程的使用使得程序能够并行计算&#xff0c;提高计…...

上传文件生成聊天机器人,实现客服、办公自动化智能体 | Chatopera

从谈论聊天机器人&#xff0c;到谈论智能体&#xff0c;是目前人工智能最炙手可热的话题&#xff0c;这两年最大的变化是大语言模型的应用。聊天机器人曾经很难定制&#xff0c;往往局限于个别行业&#xff0c;同时也只有行业内的领导者、头部企业能定制。比如银行、金融证券、…...

SD3303A 大功率高亮度LED驱动芯片IC

一般描述 SD3303A是一款大功率高亮度LED驱动芯片,可以提供1A的电流驱动3W的LED。具有高效率&#xff0c;低功耗等特点&#xff0c;适用于电池供电的LED照明设备。 SD3303A具有开路保护和过温保护。 SD3303A需要使用两颗10uF(或者更大)的瓷片电容&#xff0c;来保…...

站易WordPress

站易WordPress是一家专业提供网站建设和运营服务的公司。他们提供的服务包括企业官方网站建设、网站运营维护、网站托管、网站优化、跨境独立站建站、外贸网站建设以及海外多语言网站建设等。 此外&#xff0c;站易还提供使用现成的WordPress模板&#xff0c;这样可以快速且低…...

windows下JDK1.8安装

windows下JDK1.8安装 本文假设你知道了解基本的windows系统操作。 在Windows系统下安装JDK 1.8&#xff08;Java Development Kit&#xff09;的步骤如下&#xff1a; 步骤1&#xff1a;下载JDK 1.8 打开浏览器并访问Oracle JDK下载页面。https://www.oracle.com/java/technol…...

怎么修改Visual Studio Code中现在github账号

git config --global user.name “你的用户名” git config --global user.email “你的邮箱” git config --global --list git push -u origin your_branch_name git remote add origin...

戴尔R720服务器(3)组RAID

今天收到7块硬盘&#xff0c;现在共有8块硬盘了&#xff0c;找了个视频学习了怎么使用阵列卡组RAID并记录。 ​​ ‍ 视频参考&#xff1a;【戴尔服务器添加RAID5热备盘hotspare】 ‍ 阵列卡组RAID5 开始 连接iDRAC控制台服务器开机按F2进入BIOS选择Device Settings​ ​​…...

eNSP学习——配置高级的访问控制列表

目录 主要命令 原理概述 实验目的 实验内容 实验拓扑 实验编址 实验步骤 1、基本配置 2、搭建OSPF网络 3、配置Telnet 4、配置高级ACL控制访问 需要eNSP各种配置命令的点击链接自取&#xff1a;华为&#xff45;NSP各种设备配置命令大全PDF版_ensp配置命令大全资源-…...

oracle的bitmap索引是什么

Oracle的Bitmap索引是一种特殊的索引类型&#xff0c;主要用于处理那些数值稀疏&#xff08;low-cardinality&#xff0c;低基数&#xff09;的字段&#xff0c;特别是那些值不经常改变的字段。以下是关于Bitmap索引的详细解释&#xff1a; 定义&#xff1a; Bitmap索引是一种…...

「前端+鸿蒙」鸿蒙应用开发-TS接口-特殊用途

在 TypeScript 中&#xff0c;接口除了定义对象的结构之外&#xff0c;还有一些特殊用途&#xff0c;这些用途使得接口成为一种灵活的工具&#xff0c;用于提高代码的可维护性和可扩展性。 TS快速入门-接口-特殊用途 1. 定义函数类型 接口可以用来定义函数的类型&#xff0c;…...

Centos7系统禁用Nouveau内核驱动程序【笔记】

在CentOS系统中&#xff0c;Nouveau是开源的NVIDIA显卡驱动程序&#xff0c;但它与NVIDIA的官方驱动程序NVIDIA Proprietary Driver存在兼容性问题。 如果你想要禁用Nouveau并使用NVIDIA官方驱动&#xff0c;可以按照以下步骤操作&#xff1a; 1、创建一个黑名单文件以禁用No…...

Vue 面试通杀秘籍

理论篇&#xff1a; 1. 说说对 Vue 渐进式框架的理解&#xff08;腾讯医典&#xff09; a) 渐进式的含义&#xff1a; 主张最少, 没有多做职责之外的事 b) Vue 有些方面是不如 React&#xff0c;不如 Angular.但它是渐进的&#xff0c;没有强主张&#xff0c; 你可以在原有…...

树莓派超全系列教程文档--(61)树莓派摄像头高级使用方法

树莓派摄像头高级使用方法 配置通过调谐文件来调整相机行为 使用多个摄像头安装 libcam 和 rpicam-apps依赖关系开发包 文章来源&#xff1a; http://raspberry.dns8844.cn/documentation 原文网址 配置 大多数用例自动工作&#xff0c;无需更改相机配置。但是&#xff0c;一…...

React第五十七节 Router中RouterProvider使用详解及注意事项

前言 在 React Router v6.4 中&#xff0c;RouterProvider 是一个核心组件&#xff0c;用于提供基于数据路由&#xff08;data routers&#xff09;的新型路由方案。 它替代了传统的 <BrowserRouter>&#xff0c;支持更强大的数据加载和操作功能&#xff08;如 loader 和…...

C++.OpenGL (10/64)基础光照(Basic Lighting)

基础光照(Basic Lighting) 冯氏光照模型(Phong Lighting Model) #mermaid-svg-GLdskXwWINxNGHso {font-family:"trebuchet ms",verdana,arial,sans-serif;font-size:16px;fill:#333;}#mermaid-svg-GLdskXwWINxNGHso .error-icon{fill:#552222;}#mermaid-svg-GLd…...

HTML前端开发:JavaScript 常用事件详解

作为前端开发的核心&#xff0c;JavaScript 事件是用户与网页交互的基础。以下是常见事件的详细说明和用法示例&#xff1a; 1. onclick - 点击事件 当元素被单击时触发&#xff08;左键点击&#xff09; button.onclick function() {alert("按钮被点击了&#xff01;&…...

AI书签管理工具开发全记录(十九):嵌入资源处理

1.前言 &#x1f4dd; 在上一篇文章中&#xff0c;我们完成了书签的导入导出功能。本篇文章我们研究如何处理嵌入资源&#xff0c;方便后续将资源打包到一个可执行文件中。 2.embed介绍 &#x1f3af; Go 1.16 引入了革命性的 embed 包&#xff0c;彻底改变了静态资源管理的…...

在Mathematica中实现Newton-Raphson迭代的收敛时间算法(一般三次多项式)

考察一般的三次多项式&#xff0c;以r为参数&#xff1a; p[z_, r_] : z^3 (r - 1) z - r; roots[r_] : z /. Solve[p[z, r] 0, z]&#xff1b; 此多项式的根为&#xff1a; 尽管看起来这个多项式是特殊的&#xff0c;其实一般的三次多项式都是可以通过线性变换化为这个形式…...

LRU 缓存机制详解与实现(Java版) + 力扣解决

&#x1f4cc; LRU 缓存机制详解与实现&#xff08;Java版&#xff09; 一、&#x1f4d6; 问题背景 在日常开发中&#xff0c;我们经常会使用 缓存&#xff08;Cache&#xff09; 来提升性能。但由于内存有限&#xff0c;缓存不可能无限增长&#xff0c;于是需要策略决定&am…...

【安全篇】金刚不坏之身:整合 Spring Security + JWT 实现无状态认证与授权

摘要 本文是《Spring Boot 实战派》系列的第四篇。我们将直面所有 Web 应用都无法回避的核心问题&#xff1a;安全。文章将详细阐述认证&#xff08;Authentication) 与授权&#xff08;Authorization的核心概念&#xff0c;对比传统 Session-Cookie 与现代 JWT&#xff08;JS…...

用递归算法解锁「子集」问题 —— LeetCode 78题解析

文章目录 一、题目介绍二、递归思路详解&#xff1a;从决策树开始理解三、解法一&#xff1a;二叉决策树 DFS四、解法二&#xff1a;组合式回溯写法&#xff08;推荐&#xff09;五、解法对比 递归算法是编程中一种非常强大且常见的思想&#xff0c;它能够优雅地解决很多复杂的…...

2025年低延迟业务DDoS防护全攻略:高可用架构与实战方案

一、延迟敏感行业面临的DDoS攻击新挑战 2025年&#xff0c;金融交易、实时竞技游戏、工业物联网等低延迟业务成为DDoS攻击的首要目标。攻击呈现三大特征&#xff1a; AI驱动的自适应攻击&#xff1a;攻击流量模拟真实用户行为&#xff0c;差异率低至0.5%&#xff0c;传统规则引…...