最短路:spfa算法
最短路:spfa算法
- 题目描述
- 参考代码
题目描述
参考代码
输入示例
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算法
最短路:spfa算法 题目描述参考代码 题目描述 参考代码 输入示例 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) 最短路 迪杰斯特拉算法 初始化: 将起始节点 A 的距离设为 0。将其他所有节点的距离设为无穷大。创建一个优先队列,并将起始节点 A 加入优先队列。 处理队列: …...

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

【Three.js】知识梳理十:Three.js纹理贴图
1. 纹理贴图 在Three.js中,纹理贴图是一种将二维图像贴到三维物体表面的技术,以增强物体的视觉表现。纹理贴图可以使物体表面更加真实、细腻,为场景增色不少。 在Three.js中,纹理贴图的加载主要通过THREE.TextureLoader类实现。…...
mysql order by后跟case when
在SQL中,ORDER BY子句用于对查询结果进行排序。当在ORDER BY后面使用CASE语句时,它的原理是:根据CASE语句中定义的条件和结果,为查询结果集中的每一行生成一个临时的排序值。然后,根据这些排序值对结果集进行排序。 具…...

数字孪生赋能的智慧园区物联网云平台建设方案(97页PPT)
方案介绍: 本方案通过数字孪生技术赋能智慧园区物联网云平台,实现了园区的智能化管理、优化资源配置、提高运营效率等目标。同时提升园区的安全性、环保性和可持续性。最后,该方案还充分考虑了系统的可扩展性、安全性和可靠性,为…...
TikTok小店运营策略
TikTok,作为一款全球知名的短视频社交平台,其用户基数庞大且日活跃用户持续增长,为商家提供了巨大的商机。欧洲作为TikTok的重要市场之一,其小店功能为商家提供了一个展示和销售产品的新渠道。本文将探讨如何有效地运营TikTok小店…...
Docker面试整理-如何查看和管理Docker容器的日志?
管理和查看 Docker 容器的日志是 Docker 容器管理的重要部分,有助于监控应用的行为和诊断问题。Docker 提供了几种方法来查看和管理容器日志。 查看容器日志 要查看 Docker 容器的日志,你可以使用 docker logs 命令。这个命令会打印容器的 STDOUT 和 STDERR 输出,这是大多数…...

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

上传文件生成聊天机器人,实现客服、办公自动化智能体 | Chatopera
从谈论聊天机器人,到谈论智能体,是目前人工智能最炙手可热的话题,这两年最大的变化是大语言模型的应用。聊天机器人曾经很难定制,往往局限于个别行业,同时也只有行业内的领导者、头部企业能定制。比如银行、金融证券、…...

SD3303A 大功率高亮度LED驱动芯片IC
一般描述 SD3303A是一款大功率高亮度LED驱动芯片,可以提供1A的电流驱动3W的LED。具有高效率,低功耗等特点,适用于电池供电的LED照明设备。 SD3303A具有开路保护和过温保护。 SD3303A需要使用两颗10uF(或者更大)的瓷片电容,来保…...
站易WordPress
站易WordPress是一家专业提供网站建设和运营服务的公司。他们提供的服务包括企业官方网站建设、网站运营维护、网站托管、网站优化、跨境独立站建站、外贸网站建设以及海外多语言网站建设等。 此外,站易还提供使用现成的WordPress模板,这样可以快速且低…...
windows下JDK1.8安装
windows下JDK1.8安装 本文假设你知道了解基本的windows系统操作。 在Windows系统下安装JDK 1.8(Java Development Kit)的步骤如下: 步骤1:下载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块硬盘,现在共有8块硬盘了,找了个视频学习了怎么使用阵列卡组RAID并记录。 视频参考:【戴尔服务器添加RAID5热备盘hotspare】 阵列卡组RAID5 开始 连接iDRAC控制台服务器开机按F2进入BIOS选择Device Settings …...

eNSP学习——配置高级的访问控制列表
目录 主要命令 原理概述 实验目的 实验内容 实验拓扑 实验编址 实验步骤 1、基本配置 2、搭建OSPF网络 3、配置Telnet 4、配置高级ACL控制访问 需要eNSP各种配置命令的点击链接自取:华为eNSP各种设备配置命令大全PDF版_ensp配置命令大全资源-…...
oracle的bitmap索引是什么
Oracle的Bitmap索引是一种特殊的索引类型,主要用于处理那些数值稀疏(low-cardinality,低基数)的字段,特别是那些值不经常改变的字段。以下是关于Bitmap索引的详细解释: 定义: Bitmap索引是一种…...
「前端+鸿蒙」鸿蒙应用开发-TS接口-特殊用途
在 TypeScript 中,接口除了定义对象的结构之外,还有一些特殊用途,这些用途使得接口成为一种灵活的工具,用于提高代码的可维护性和可扩展性。 TS快速入门-接口-特殊用途 1. 定义函数类型 接口可以用来定义函数的类型,…...

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

Vue 面试通杀秘籍
理论篇: 1. 说说对 Vue 渐进式框架的理解(腾讯医典) a) 渐进式的含义: 主张最少, 没有多做职责之外的事 b) Vue 有些方面是不如 React,不如 Angular.但它是渐进的,没有强主张, 你可以在原有…...

抖音增长新引擎:品融电商,一站式全案代运营领跑者
抖音增长新引擎:品融电商,一站式全案代运营领跑者 在抖音这个日活超7亿的流量汪洋中,品牌如何破浪前行?自建团队成本高、效果难控;碎片化运营又难成合力——这正是许多企业面临的增长困局。品融电商以「抖音全案代运营…...
【算法训练营Day07】字符串part1
文章目录 反转字符串反转字符串II替换数字 反转字符串 题目链接:344. 反转字符串 双指针法,两个指针的元素直接调转即可 class Solution {public void reverseString(char[] s) {int head 0;int end s.length - 1;while(head < end) {char temp …...
什么是EULA和DPA
文章目录 EULA(End User License Agreement)DPA(Data Protection Agreement)一、定义与背景二、核心内容三、法律效力与责任四、实际应用与意义 EULA(End User License Agreement) 定义: EULA即…...
leetcodeSQL解题:3564. 季节性销售分析
leetcodeSQL解题:3564. 季节性销售分析 题目: 表:sales ---------------------- | Column Name | Type | ---------------------- | sale_id | int | | product_id | int | | sale_date | date | | quantity | int | | price | decimal | -…...
Java线上CPU飙高问题排查全指南
一、引言 在Java应用的线上运行环境中,CPU飙高是一个常见且棘手的性能问题。当系统出现CPU飙高时,通常会导致应用响应缓慢,甚至服务不可用,严重影响用户体验和业务运行。因此,掌握一套科学有效的CPU飙高问题排查方法&…...
rnn判断string中第一次出现a的下标
# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...
Python ROS2【机器人中间件框架】 简介
销量过万TEEIS德国护膝夏天用薄款 优惠券冠生园 百花蜂蜜428g 挤压瓶纯蜂蜜巨奇严选 鞋子除臭剂360ml 多芬身体磨砂膏280g健70%-75%酒精消毒棉片湿巾1418cm 80片/袋3袋大包清洁食品用消毒 优惠券AIMORNY52朵红玫瑰永生香皂花同城配送非鲜花七夕情人节生日礼物送女友 热卖妙洁棉…...

保姆级教程:在无网络无显卡的Windows电脑的vscode本地部署deepseek
文章目录 1 前言2 部署流程2.1 准备工作2.2 Ollama2.2.1 使用有网络的电脑下载Ollama2.2.2 安装Ollama(有网络的电脑)2.2.3 安装Ollama(无网络的电脑)2.2.4 安装验证2.2.5 修改大模型安装位置2.2.6 下载Deepseek模型 2.3 将deepse…...
LangChain知识库管理后端接口:数据库操作详解—— 构建本地知识库系统的基础《二》
这段 Python 代码是一个完整的 知识库数据库操作模块,用于对本地知识库系统中的知识库进行增删改查(CRUD)操作。它基于 SQLAlchemy ORM 框架 和一个自定义的装饰器 with_session 实现数据库会话管理。 📘 一、整体功能概述 该模块…...
多模态图像修复系统:基于深度学习的图片修复实现
多模态图像修复系统:基于深度学习的图片修复实现 1. 系统概述 本系统使用多模态大模型(Stable Diffusion Inpainting)实现图像修复功能,结合文本描述和图片输入,对指定区域进行内容修复。系统包含完整的数据处理、模型训练、推理部署流程。 import torch import numpy …...