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

邮递员送信 单源最短路+反向建边

有一个邮递员要送东西,邮局在节点 1 1 1。他总共要送 n − 1 n−1 n1样东西,其目的地分别是节点 2 2 2到节点 n n n。所有的道路都是单行的,共有 m m m条道路。邮递员每次只能带一样东西,运送每件物品过后必须返回邮局。求送完东西后回到邮局最少需要的时间。
首先送信时,从 1 1 1 2 − n 2-n 2n就是标准的单源最短路;而返回的时候就是多到一,多源最短路比较麻烦。这时候我们邻接矩阵倒过来,从多到一的最短路变式的路径“反向建边”,就变成一到多的单源最短路。

#include<bits/stdc++.h>
using namespace std;
struct node
{int u,v,w,next;
}a[100010],b[100010];
struct New
{int w,now;bool operator <(const New &x)const{return w>x.w;}
};
priority_queue <New> q;
int head[10010],bhead[10010],dis[10010],flag[10010];
int n,m,s,num1,num2,ans=0,x,y;
void add(int u,int v,int w)
{a[++num1].v=v;a[num1].w=w;a[num1].next=head[u];head[u]=num1;b[++num2].v=u;b[num2].w=w;b[num2].next=bhead[v];bhead[v]=num2;
}
void Dij()
{for(int i=1;i<=n;i++)dis[i]=9999999;dis[1]=0;memset(flag,0,sizeof(flag));q.push((New){0,1});while(!q.empty()){New X=q.top();q.pop();int U=X.now;if(flag[U]==1)continue;flag[U]=1;for(int i=head[U];i;i=a[i].next){int V=a[i].v;if(dis[V]>dis[U]+a[i].w){dis[V]=dis[U]+a[i].w;q.push((New){dis[V],V});}}}
}
void Dij2()
{for(int i=1;i<=n;i++)dis[i]=9999999;memset(flag,0,sizeof(flag));dis[1]=0;q.push((New){0,1});while(!q.empty()){New X=q.top();q.pop();int U=X.now;if(flag[U]==1)continue;flag[U]=1;for(int i=bhead[U];i;i=b[i].next){int V=b[i].v;if(dis[V]>dis[U]+b[i].w){dis[V]=dis[U]+b[i].w;q.push((New){dis[V],V});}}}
}
int main()
{cin>>n>>m;for(int i=1;i<=m;i++){cin>>x>>y>>s;add(x,y,s);}Dij();for(int i=2;i<=n;i++)ans+=dis[i];Dij2();for(int i=2;i<=n;i++)ans+=dis[i];cout<<ans<<endl;return 0;
}

相关文章:

邮递员送信 单源最短路+反向建边

有一个邮递员要送东西&#xff0c;邮局在节点 1 1 1。他总共要送 n − 1 n−1 n−1样东西&#xff0c;其目的地分别是节点 2 2 2到节点 n n n。所有的道路都是单行的&#xff0c;共有 m m m条道路。邮递员每次只能带一样东西&#xff0c;运送每件物品过后必须返回邮局。求送完东…...

git的常用操作

1. git查看dev分支与master分支的情况 要查看特定分支&#xff08;如dev和master&#xff09;的情况&#xff0c;您可以使用以下命令&#xff1a; git log --oneline master..dev 这将显示在dev分支上存在但不在master分支上的提交记录的简要信息。每条记录都包括提交的哈希…...

vscode搭建java开发环境

一、配置extensions环境变量VSCODE_EXTENSIONS&#xff0c; 该环境变量路径下的存放安装组件&#xff1a; 二、setting配置文件 {"java.jdt.ls.java.home": "e:\\software\\jdk\\jdk17",// java运行环境"java.configuration.runtimes": [{"…...

01 qt快速入门

一 qt介绍 1.基本概念 1991年由Qt Company(奇趣)开发的跨平台C++图形用户界面应用程序开发框架,GUI程序和非GUI程序。优点:一套源码在不同的平台通过不同的编译器进行编译,就可以运行到该平台上目标机。面向对象的封装机制来对其接口封装。 GUI —图形用户界面(Graphic…...

嵌入式开发中常用且杂散的命令

1、mount命令 # 挂载linux系统 mkdir /tmp/share mount -t nfs 10.77.66.88:/share/ /tmp/share -o nolock,tcp cd /tmp/share# 挂载Windows系统 mkdir /tmp/windows mount -t nfs 10.66.77.88:/c/public /tmp/windows -o nolock,tcp cd /tmp/windows# 挂载vfat格式的U盘 mkdi…...

JS导出复杂多级表头的Excel

使用方式 1、安装依赖 npm install xlsx-js-style2、复制代码文件exportExcel.js至工程 https://github.com/EnthuDai/export-excel-in-one-line 3、在引入excel.js后调用 Excel.export(columns, dataSource, 导出文件名)4、代码demo 5、效果 页面excel 适用范围 对于使…...

2023国赛数学建模E题思路分析

文章目录 0 赛题思路1 竞赛信息2 竞赛时间3 建模常见问题类型3.1 分类问题3.2 优化问题3.3 预测问题3.4 评价问题 4 建模资料 0 赛题思路 &#xff08;赛题出来以后第一时间在CSDN分享&#xff09; https://blog.csdn.net/dc_sinor?typeblog 1 竞赛信息 全国大学生数学建模…...

【JavaScript 12】二进制位运算符 或 与 非 异或 左移 右移 头部补零右移

二进制位运算符 概述 概述 7个用于直接对二进制位进行运算 二进制或 or | 若两个二进制位都为0则为0&#xff0c;否则为1二进制与 and & 若两个二进制位都为1则为1&#xff0c;否则为0二进制非 not ~ 对一个二进制位取反异或 xor ^ 若两个二进制位不同则为1&#xff0c;否…...

Kafka 入门到起飞 - Kafka是怎么保证可靠性的呢

在这里插入图片描述 我们已经了解到&#xff0c;复习一下 创建topic时&#xff0c;可以指定副本因子 repilication-factor 3 表示分区的副本数&#xff0c;包括Leader分区副本和follower分区副本不要超过broker的数量&#xff0c;尽量保证一个分区的副本均匀分散不同的broker…...

数学建模(三)整数规划

视频推荐&#xff1a;B站_数学建模老哥 一、整数规划基本原理 数学规划中的变量&#xff08;部分或全部&#xff09;限制为整数时&#xff0c;称为整数规划。若在线性规划模型中&#xff0c;变量限制为整数&#xff0c;则称为整数线性规划。目前所流行的求解整数规划的方法&am…...

全面梳理Python下的NLP 库

一、说明 Python 对自然语言处理库有丰富的支持。从文本处理、标记化文本并确定其引理开始&#xff0c;到句法分析、解析文本并分配句法角色&#xff0c;再到语义处理&#xff0c;例如识别命名实体、情感分析和文档分类&#xff0c;一切都由至少一个库提供。那么&#xff0c;你…...

系统设计类题目汇总三

20 秒杀系统的一些拓展和优化 20.1 你发送消息时&#xff0c;流程是将消息发送给MQ做异步处理&#xff0c;然后消费者去消费消息&#xff0c;之后调用运营商的发送消息接口&#xff0c;那如果调用运营商的接口后消息发送失败怎么办&#xff1f; 确实&#xff0c;对于这种核心…...

“深入解析JVM:探索Java虚拟机的内部工作原理“

标题&#xff1a;深入解析JVM&#xff1a;探索Java虚拟机的内部工作原理 摘要&#xff1a;本文将深入解析Java虚拟机&#xff08;JVM&#xff09;的内部工作原理&#xff0c;包括类加载、内存管理、垃圾回收、即时编译等关键概念。通过对这些概念的详细讲解和示例代码的演示&a…...

VB+sql小型超市管理系统设计与实现

1、项目计划 1.1系统开发目的 (1)大大提高超市的运作效率; (2)通过全面的信息采集和处理,辅助提高超市的决策水平; (3)使用本系统,可以迅速提升超市的管理水平,为降低经营成本, 提高效益,增强超市扩张力, 提供有效的技术保障。 1.2背景说明 21世纪,超市的…...

mysql面试

基础篇 通用语法及分类 DDL: 数据定义语言&#xff0c;用来定义数据库对象&#xff08;数据库、表、字段&#xff09;DML: 数据操作语言&#xff0c;用来对数据库表中的数据进行增删改DQL: 数据查询语言&#xff0c;用来查询数据库中表的记录DCL: 数据控制语言&#xff0c;用…...

3.1 Ansible 的使用和配置管理

Ansible 的使用和配置管理 文章目录 Ansible 的使用和配置管理Ansible 基础Ansible 模块和变量主机管理和组织角色和剧本部署应用和配置自动化与批量操作Ansible 常见用例Ansible 最佳实践和性能优化 大纲 Ansible 简介和特点 介绍 Ansible 的定义和作用&#xff0c;以及它在配…...

神经网络基础-神经网络补充概念-06-计算图

概念 “计算图”&#xff08;Computational Graph&#xff09;是一种用于表示数学表达式计算过程的图结构&#xff0c;广泛用于深度学习和自动微分等领域。计算图将复杂的数学表达式分解为一系列简单的计算节点&#xff0c;这些节点之间通过边连接&#xff0c;形成了一个有向无…...

【【STM32之GPIO】】

STM32之GPIO 学完了正点原子自带的视频课之后感觉仍然一知半解现在更新一下来自其他版本的STM32学习 GPIO 就是 General Purpose Input Output 中文名叫通用输入输出口 可配置8种输入输出模式 引脚电平 0V~3.3V 部分引脚可容忍5V 输出模式下可控制端口输出高低电平&#xff…...

【动画】p60动画蓝图、播放蒙太奇、打包

p60动画蓝图、播放蒙太奇、打包 p60动画蓝图、播放蒙太奇、打包添加动画动画蓝图使模型使用动画蓝图奔跑跳舞蒙太奇 移动打断蒙太奇打包退出游戏 p60动画蓝图、播放蒙太奇、打包 添加动画 右键内容浏览器-》动画-》混合空间1D-》选择新的角色的骨骼 如下图在资产详情修改参数…...

去趋势化一个心电图信号、信号功率谱、低通IIR滤波器并平滑信号、对滤波器引起的延迟进行补偿研究(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

(二)TensorRT-LLM | 模型导出(v0.20.0rc3)

0. 概述 上一节 对安装和使用有个基本介绍。根据这个 issue 的描述&#xff0c;后续 TensorRT-LLM 团队可能更专注于更新和维护 pytorch backend。但 tensorrt backend 作为先前一直开发的工作&#xff0c;其中包含了大量可以学习的地方。本文主要看看它导出模型的部分&#x…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

AI编程--插件对比分析:CodeRider、GitHub Copilot及其他

AI编程插件对比分析&#xff1a;CodeRider、GitHub Copilot及其他 随着人工智能技术的快速发展&#xff0c;AI编程插件已成为提升开发者生产力的重要工具。CodeRider和GitHub Copilot作为市场上的领先者&#xff0c;分别以其独特的特性和生态系统吸引了大量开发者。本文将从功…...

DeepSeek 技术赋能无人农场协同作业:用 AI 重构农田管理 “神经网”

目录 一、引言二、DeepSeek 技术大揭秘2.1 核心架构解析2.2 关键技术剖析 三、智能农业无人农场协同作业现状3.1 发展现状概述3.2 协同作业模式介绍 四、DeepSeek 的 “农场奇妙游”4.1 数据处理与分析4.2 作物生长监测与预测4.3 病虫害防治4.4 农机协同作业调度 五、实际案例大…...

Linux C语言网络编程详细入门教程:如何一步步实现TCP服务端与客户端通信

文章目录 Linux C语言网络编程详细入门教程&#xff1a;如何一步步实现TCP服务端与客户端通信前言一、网络通信基础概念二、服务端与客户端的完整流程图解三、每一步的详细讲解和代码示例1. 创建Socket&#xff08;服务端和客户端都要&#xff09;2. 绑定本地地址和端口&#x…...

JS手写代码篇----使用Promise封装AJAX请求

15、使用Promise封装AJAX请求 promise就有reject和resolve了&#xff0c;就不必写成功和失败的回调函数了 const BASEURL ./手写ajax/test.jsonfunction promiseAjax() {return new Promise((resolve, reject) > {const xhr new XMLHttpRequest();xhr.open("get&quo…...

【C++进阶篇】智能指针

C内存管理终极指南&#xff1a;智能指针从入门到源码剖析 一. 智能指针1.1 auto_ptr1.2 unique_ptr1.3 shared_ptr1.4 make_shared 二. 原理三. shared_ptr循环引用问题三. 线程安全问题四. 内存泄漏4.1 什么是内存泄漏4.2 危害4.3 避免内存泄漏 五. 最后 一. 智能指针 智能指…...

Webpack性能优化:构建速度与体积优化策略

一、构建速度优化 1、​​升级Webpack和Node.js​​ ​​优化效果​​&#xff1a;Webpack 4比Webpack 3构建时间降低60%-98%。​​原因​​&#xff1a; V8引擎优化&#xff08;for of替代forEach、Map/Set替代Object&#xff09;。默认使用更快的md4哈希算法。AST直接从Loa…...

解析奥地利 XARION激光超声检测系统:无膜光学麦克风 + 无耦合剂的技术协同优势及多元应用

在工业制造领域&#xff0c;无损检测&#xff08;NDT)的精度与效率直接影响产品质量与生产安全。奥地利 XARION开发的激光超声精密检测系统&#xff0c;以非接触式光学麦克风技术为核心&#xff0c;打破传统检测瓶颈&#xff0c;为半导体、航空航天、汽车制造等行业提供了高灵敏…...