邮递员送信 单源最短路+反向建边
有一个邮递员要送东西,邮局在节点 1 1 1。他总共要送 n − 1 n−1 n−1样东西,其目的地分别是节点 2 2 2到节点 n n n。所有的道路都是单行的,共有 m m m条道路。邮递员每次只能带一样东西,运送每件物品过后必须返回邮局。求送完东西后回到邮局最少需要的时间。
首先送信时,从 1 1 1到 2 − n 2-n 2−n就是标准的单源最短路;而返回的时候就是多到一,多源最短路比较麻烦。这时候我们邻接矩阵倒过来,从多到一的最短路变式的路径“反向建边”,就变成一到多的单源最短路。
#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;
}
相关文章:
邮递员送信 单源最短路+反向建边
有一个邮递员要送东西,邮局在节点 1 1 1。他总共要送 n − 1 n−1 n−1样东西,其目的地分别是节点 2 2 2到节点 n n n。所有的道路都是单行的,共有 m m m条道路。邮递员每次只能带一样东西,运送每件物品过后必须返回邮局。求送完东…...
git的常用操作
1. git查看dev分支与master分支的情况 要查看特定分支(如dev和master)的情况,您可以使用以下命令: git log --oneline master..dev 这将显示在dev分支上存在但不在master分支上的提交记录的简要信息。每条记录都包括提交的哈希…...
vscode搭建java开发环境
一、配置extensions环境变量VSCODE_EXTENSIONS, 该环境变量路径下的存放安装组件: 二、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 赛题思路 (赛题出来以后第一时间在CSDN分享) https://blog.csdn.net/dc_sinor?typeblog 1 竞赛信息 全国大学生数学建模…...
【JavaScript 12】二进制位运算符 或 与 非 异或 左移 右移 头部补零右移
二进制位运算符 概述 概述 7个用于直接对二进制位进行运算 二进制或 or | 若两个二进制位都为0则为0,否则为1二进制与 and & 若两个二进制位都为1则为1,否则为0二进制非 not ~ 对一个二进制位取反异或 xor ^ 若两个二进制位不同则为1,否…...
Kafka 入门到起飞 - Kafka是怎么保证可靠性的呢
在这里插入图片描述 我们已经了解到,复习一下 创建topic时,可以指定副本因子 repilication-factor 3 表示分区的副本数,包括Leader分区副本和follower分区副本不要超过broker的数量,尽量保证一个分区的副本均匀分散不同的broker…...
数学建模(三)整数规划
视频推荐:B站_数学建模老哥 一、整数规划基本原理 数学规划中的变量(部分或全部)限制为整数时,称为整数规划。若在线性规划模型中,变量限制为整数,则称为整数线性规划。目前所流行的求解整数规划的方法&am…...
全面梳理Python下的NLP 库
一、说明 Python 对自然语言处理库有丰富的支持。从文本处理、标记化文本并确定其引理开始,到句法分析、解析文本并分配句法角色,再到语义处理,例如识别命名实体、情感分析和文档分类,一切都由至少一个库提供。那么,你…...
系统设计类题目汇总三
20 秒杀系统的一些拓展和优化 20.1 你发送消息时,流程是将消息发送给MQ做异步处理,然后消费者去消费消息,之后调用运营商的发送消息接口,那如果调用运营商的接口后消息发送失败怎么办? 确实,对于这种核心…...
“深入解析JVM:探索Java虚拟机的内部工作原理“
标题:深入解析JVM:探索Java虚拟机的内部工作原理 摘要:本文将深入解析Java虚拟机(JVM)的内部工作原理,包括类加载、内存管理、垃圾回收、即时编译等关键概念。通过对这些概念的详细讲解和示例代码的演示&a…...
VB+sql小型超市管理系统设计与实现
1、项目计划 1.1系统开发目的 (1)大大提高超市的运作效率; (2)通过全面的信息采集和处理,辅助提高超市的决策水平; (3)使用本系统,可以迅速提升超市的管理水平,为降低经营成本, 提高效益,增强超市扩张力, 提供有效的技术保障。 1.2背景说明 21世纪,超市的…...
mysql面试
基础篇 通用语法及分类 DDL: 数据定义语言,用来定义数据库对象(数据库、表、字段)DML: 数据操作语言,用来对数据库表中的数据进行增删改DQL: 数据查询语言,用来查询数据库中表的记录DCL: 数据控制语言,用…...
3.1 Ansible 的使用和配置管理
Ansible 的使用和配置管理 文章目录 Ansible 的使用和配置管理Ansible 基础Ansible 模块和变量主机管理和组织角色和剧本部署应用和配置自动化与批量操作Ansible 常见用例Ansible 最佳实践和性能优化 大纲 Ansible 简介和特点 介绍 Ansible 的定义和作用,以及它在配…...
神经网络基础-神经网络补充概念-06-计算图
概念 “计算图”(Computational Graph)是一种用于表示数学表达式计算过程的图结构,广泛用于深度学习和自动微分等领域。计算图将复杂的数学表达式分解为一系列简单的计算节点,这些节点之间通过边连接,形成了一个有向无…...
【【STM32之GPIO】】
STM32之GPIO 学完了正点原子自带的视频课之后感觉仍然一知半解现在更新一下来自其他版本的STM32学习 GPIO 就是 General Purpose Input Output 中文名叫通用输入输出口 可配置8种输入输出模式 引脚电平 0V~3.3V 部分引脚可容忍5V 输出模式下可控制端口输出高低电平ÿ…...
【动画】p60动画蓝图、播放蒙太奇、打包
p60动画蓝图、播放蒙太奇、打包 p60动画蓝图、播放蒙太奇、打包添加动画动画蓝图使模型使用动画蓝图奔跑跳舞蒙太奇 移动打断蒙太奇打包退出游戏 p60动画蓝图、播放蒙太奇、打包 添加动画 右键内容浏览器-》动画-》混合空间1D-》选择新的角色的骨骼 如下图在资产详情修改参数…...
去趋势化一个心电图信号、信号功率谱、低通IIR滤波器并平滑信号、对滤波器引起的延迟进行补偿研究(Matlab代码实现)
💥💥💞💞欢迎来到本博客❤️❤️💥💥 🏆博主优势:🌞🌞🌞博客内容尽量做到思维缜密,逻辑清晰,为了方便读者。 ⛳️座右铭&a…...
嵌入式开发调试宏与性能优化实战
1. 嵌入式开发调试宏的妙用在嵌入式开发中,调试是最耗时耗力的环节之一。每次修改代码后都需要重新烧录、运行、观察结果,这个过程往往要重复数十次。而合理使用编译器提供的调试宏,可以大幅提升调试效率。1.1 基础调试宏解析GCC编译器提供了…...
03 MongoDB文档的各种增加、更新、删除操作总结
更多内容请见: 《深入掌握MongoDB数据库》 - 专栏介绍和目录 一. 插入文档 注意: 在 MongoDB 中,直接插入内容会自动创建集合! 1.1 使用insert()方法 语法格式: db.COLLECTION_NAME.insert(document) 说明: 若插入的数据主键已经存在,则会抛 org.springframework.dao.Du…...
用C#和ONNX Runtime搞定车牌识别:从模型部署到双层车牌分割的实战避坑
C#与ONNX Runtime实战:车牌识别系统开发全流程与双层车牌处理精要 车牌识别技术已经从实验室走向了各行各业,从停车场管理到交通执法,再到智慧城市建设,这项技术正在改变我们与车辆的交互方式。作为一名长期奋战在计算机视觉一线的…...
5分钟学会OrgChart:从零开始创建动态组织图
5分钟学会OrgChart:从零开始创建动态组织图 【免费下载链接】OrgChart Its a simple and direct organization chart plugin. Anytime you want a tree-like chart, you can turn to OrgChart. 项目地址: https://gitcode.com/gh_mirrors/or/OrgChart 如果你…...
cool-admin(midway版)前端路由缓存:include与exclude配置策略
cool-admin(midway版)前端路由缓存:include与exclude配置策略 【免费下载链接】cool-admin-midway 🔥 cool-admin(midway版)一个很酷的后台权限管理框架,模块化、插件化、CRUD极速开发,永久开源免费,基于midway.js 3.x…...
英雄联盟智能助手:如何在选人阶段获得不公平优势?终极指南揭秘本地化工具LeagueAkari
英雄联盟智能助手:如何在选人阶段获得不公平优势?终极指南揭秘本地化工具LeagueAkari 【免费下载链接】League-Toolkit An all-in-one toolkit for LeagueClient. Gathering power 🚀. 项目地址: https://gitcode.com/gh_mirrors/le/League…...
Hotkey Detective:3步快速解决Windows热键冲突,找出占用快捷键的幕后黑手
Hotkey Detective:3步快速解决Windows热键冲突,找出占用快捷键的幕后黑手 【免费下载链接】hotkey-detective A small program for investigating stolen key combinations under Windows 7 and later. 项目地址: https://gitcode.com/gh_mirrors/ho/h…...
【ZGC性能调优终极指南】:20年JVM专家亲授5大实战瓶颈突破法
第一章:ZGC核心机制与性能边界全景透视ZGC(Z Garbage Collector)是JDK 11引入的低延迟垃圾收集器,专为处理TB级堆内存与毫秒级停顿目标而设计。其核心突破在于并发标记、并发重定位与着色指针(Colored Pointers&#x…...
从‘torch not found’到成功训练:一个YOLOv8环境配置的完整避坑实录(含CUDA/cuDNN版本选择)
YOLOv8环境配置终极指南:从版本匹配到显存优化的全流程实战 在计算机视觉领域,YOLOv8作为目标检测的标杆算法,其安装配置过程却常常成为开发者的"拦路虎"。本文将带你系统解决从PyTorch版本选择、CUDA环境配置到显存优化的全链路问…...
2025年11月一区SCI-壁虎优化算法Gekko Japonicus Algorithm-附Matlab免费代码
引言 近年来,在合理框架内求解优化问题的元启发式算法的发展引起了全球科学界的极大关注。本期介绍一种新的创新算法——壁虎优化算法Gekko Japonicus Algorithm,GJA。该算法的灵感主要来自于壁虎的捕食策略和生存行为。通过模拟壁虎的混合运动模式、定…...
