当前位置: 首页 > 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…...

Python 如何反向 `enumerate` 遍历枚举

在 Python 中&#xff0c;enumerate() 是一个常用的内置函数&#xff0c;用于在遍历可迭代对象&#xff08;如列表、元组、字符串等&#xff09;时同时获取索引和值。但默认情况下&#xff0c;enumerate() 是从前往后遍历的。那么&#xff0c;**如何反向 enumerate 遍历&#x…...

资源提取高效解析与跨设备管理:猫抓浏览器扩展的技术实践

资源提取高效解析与跨设备管理&#xff1a;猫抓浏览器扩展的技术实践 【免费下载链接】cat-catch 猫抓 浏览器资源嗅探扩展 / cat-catch Browser Resource Sniffing Extension 项目地址: https://gitcode.com/GitHub_Trending/ca/cat-catch 在数字化内容爆炸的今天&…...

避坑指南:PICO空间网格开发常见问题排查(视频透视/组件配置/真机调试)

PICO空间网格开发实战&#xff1a;视频透视配置与真机调试全解析 在混合现实&#xff08;MR&#xff09;开发领域&#xff0c;PICO设备凭借其出色的空间感知能力为开发者提供了广阔的创新空间。然而&#xff0c;当我们将Unity引擎与PICO硬件结合进行空间网格开发时&#xff0c;…...

CANoe Trace中的Time列:从基础定义到高级时序分析实战

1. CANoe Trace中的Time列基础解析 第一次打开CANoe的Trace窗口时&#xff0c;那排密密麻麻的数据确实让人头皮发麻。但别担心&#xff0c;咱们先来搞定最左边那个看似简单却至关重要的Time列。这个时间戳就像车载网络的"心电图"记录仪&#xff0c;精确到微秒级别地记…...

Postman实战指南:深入解析CORS预检请求与响应头配置

1. 为什么CORS会成为开发者的噩梦&#xff1f; 第一次遇到CORS问题时&#xff0c;我盯着浏览器控制台那个鲜红的报错信息整整发呆了十分钟。"Access-Control-Allow-Origin"这个看起来人畜无害的响应头&#xff0c;竟然能让整个前端应用瘫痪。后来才发现&#xff0c;这…...

Qwen3-TTS开源模型教程:Gradio接口封装+API服务发布完整指南

Qwen3-TTS开源模型教程&#xff1a;Gradio接口封装API服务发布完整指南 1. 前言&#xff1a;为什么你需要一个专属的语音合成服务&#xff1f; 想象一下&#xff0c;你正在开发一个智能客服应用&#xff0c;需要为不同国家的用户提供多语言的语音回复&#xff1b;或者你是一个…...

RobotStudio机器人轨迹规划:从工件坐标到流畅路径的实战指南

1. 工件坐标系的创建与校准 在RobotStudio中规划机器人轨迹的第一步&#xff0c;就是建立准确的工件坐标系。这就像盖房子前要先打好地基&#xff0c;坐标系就是机器人运动的"地基"。我见过不少新手直接开始示教点位&#xff0c;结果发现机器人总是跑偏&#xff0c;就…...

从播放卡顿到流媒体优化:深入MP4的stbl盒子,理解视频流畅播放的关键

从播放卡顿到流媒体优化&#xff1a;深入MP4的stbl盒子&#xff0c;理解视频流畅播放的关键 当你在深夜调试一个在线视频播放器&#xff0c;发现用户总是抱怨卡顿和拖拽不准时&#xff0c;是否曾思考过问题可能隐藏在MP4文件最核心的stbl盒子中&#xff1f;作为流媒体开发者&am…...

ERNIE-4.5-0.3B-PT智能合约分析:区块链安全检测系统

ERNIE-4.5-0.3B-PT智能合约分析&#xff1a;区块链安全检测系统 1. 引言 区块链开发者们经常面临一个头疼的问题&#xff1a;智能合约部署后才发现存在安全漏洞&#xff0c;导致资产损失。传统的安全审计需要专业团队花费数天甚至数周时间&#xff0c;成本高昂且效率低下。现…...

Linux 中的硬链接和软连接是什么,二者有什么区别?

在 Linux 文件系统中&#xff0c;**硬链接&#xff08;Hard Link&#xff09;和软链接&#xff08;Soft Link&#xff0c;又称符号链接 Symbolic Link&#xff09;**是两种不同的文件引用方式。它们都允许用户通过不同的路径访问同一个文件内容&#xff0c;但它们的实现机制、限…...