P1629 邮递员送信(最短路)(内附封面)

邮递员送信

题目描述

有一个邮递员要送东西,邮局在节点 1 1 1。他总共要送 n − 1 n-1 n1 样东西,其目的地分别是节点 2 2 2 到节点 n n n。由于这个城市的交通比较繁忙,因此所有的道路都是单行的,共有 m m m 条道路。这个邮递员每次只能带一样东西,并且运送每件物品过后必须返回邮局。求送完这 n − 1 n-1 n1 样东西并且最终回到邮局最少需要的时间。

输入格式

第一行包括两个整数, n n n m m m,表示城市的节点数量和道路数量。

第二行到第 ( m + 1 ) (m+1) (m+1) 行,每行三个整数, u , v , w u,v,w u,v,w,表示从 u u u v v v 有一条通过时间为 w w w 的道路。

输出格式

输出仅一行,包含一个整数,为最少需要的时间。

样例 #1

样例输入 #1

5 10
2 3 5
1 5 5
3 5 6
1 2 8
1 3 8
5 3 4
4 1 8
4 5 3
3 5 6
5 4 2

样例输出 #1

83

提示

对于 30 % 30\% 30% 的数据, 1 ≤ n ≤ 200 1 \leq n \leq 200 1n200

对于 100 % 100\% 100% 的数据, 1 ≤ n ≤ 1 0 3 1 \leq n \leq 10^3 1n103 1 ≤ m ≤ 1 0 5 1 \leq m \leq 10^5 1m105 1 ≤ u , v ≤ n 1\leq u,v \leq n 1u,vn 1 ≤ w ≤ 1 0 4 1 \leq w \leq 10^4 1w104,输入保证任意两点都能互相到达。

F l o y d Floyd Floyd 逃课做法(要开O2)

直接套 F l o y d Floyd Floyd

最后的结果是每个点到 1 节点的距离与 1 到每个点的距离之和,注意存储初始距离时保留最短的一条,否则会WA

F l o y d Floyd Floyd做法代码

#include<bits/stdc++.h>
using namespace std;
const int N=1e3+111;
int n,m,ans=0;
int dis[N][N];
int main(){cin>>n>>m;memset(dis,0x3f,sizeof(dis));for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;dis[u][v]=min(dis[u][v],w);//dis[u][v]=w;}for(int k=1;k<=n;k++){for(int i=1;i<=n;i++){for(int j=1;j<=n;j++){dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);}}}for(int i=2;i<=n;i++){ans+=dis[i][1]+dis[1][i];}cout<<ans<<endl;return 0;
}

d i j k s t r a dijkstra dijkstra堆优化

1 1 1 跑到其他 2 n 2~n 2 n 节点需要跑一遍 d i j k s t r a dijkstra dijkstra

返回 1 1 1节点也需要跑一遍 d i j k s t r a dijkstra dijkstra

因此我们在 u + n u+n u+n v + n v+n v+n 建一个反图,方便反跑

需要堆优化

答案累加 2 2 2累加到 n n n,反跑后从 2 + n 2+n 2+n 累加到 n ∗ 2 n*2 n2即可

AC CODE

#include<bits/stdc++.h>
using namespace std;
const int N=1e4+49999;
int n,m,ans=0;
int dis[N];
vector<pair<int,int> > a[N];
bool vis[N];
void dijkstra(int s){priority_queue<pair<int,int>,vector<pair<int,int> >,greater<pair<int,int> > >q;memset(dis,0x3f,sizeof(dis));memset(vis,0,sizeof(vis));dis[s]=0;q.push({0,s});while(!q.empty()){pair<int,int> tmp=q.top();q.pop();int x=tmp.second;int y=tmp.first;if(dis[x]<tmp.first)continue;if(vis[x]==1)continue;vis[x]=1;for(int i=0;i<a[x].size();i++){if(dis[a[x][i].first]>y+a[x][i].second){dis[a[x][i].first]=y+a[x][i].second;q.push({dis[a[x][i].first],a[x][i].first});}}}
}
int main(){cin>>n>>m;for(int i=1;i<=m;i++){int u,v,w;cin>>u>>v>>w;a[u].emplace_back(make_pair(v,w));a[v+n].emplace_back(make_pair(u+n,w));}dijkstra(1);for(int i=2;i<=n;i++){ans+=dis[i];}dijkstra(1+n);for(int i=2+n;i<=n*2;i++){ans+=dis[i];}cout<<ans<<endl;return 0;
}

附封面(碧蓝档案)

请添加图片描述

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/79865.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

嵌入式:C高级 Day4

一、整理思维导图 二、写一个函数&#xff0c;获取用户的uid和gid并使用变量接收 三、整理冒泡排序、简单选择排序和快速排序的代码 冒泡排序 #include <myhead.h>void output(int arr[], int len); void bubble_sort(int arr[], int len);int main(int argc, const ch…

摄像机终端IP地址白名单配置流程

海康摄像头配置白名单流程 1.登录海康摄像机前端 2.进入配置-系统-安全管理-IP地址过滤 3.IP地址过滤方式选择“允许” 4.点击添加按钮输入对应的IP地址或者IP网段 5.最后勾选启用IP地址过滤&#xff0c;然后保存 大华摄像头配置白名单流程 1.登录大华摄像机前端 2.进入设…

怎么样通过Bootstrap已经编译好(压缩好)的源码去查看符合阅读习惯的源码【通过Source Map(源映射)文件实现】

阅读本篇博文前&#xff0c;建议大家先看看下面这篇博文&#xff1a; https://blog.csdn.net/wenhao_ir/article/details/132089650 Bootstrap经编译(压缩)后的源码百度网盘下载地址&#xff1a; https://pan.baidu.com/s/14BM9gpC3K-LKxhyLGh4J9Q?pwdm02m Bootstrap未经编译…

优化手机性能,解决卡顿问题:关闭这3个微信开关,释放内存空间

在日常使用手机的过程中&#xff0c;微信无疑是受欢迎和广泛使用的社交应用之一。然而&#xff0c;由于微信的一些默认设置可能会占用大量内存空间&#xff0c;导致手机性能下降并出现卡顿问题。为了提高手机的运行效果&#xff0c;我们需要注意并关闭这3个微信开关&#xff0c…

什么样的跨网文件安全交换系统 可实现安全便捷的文件摆渡?

进入互联网时代&#xff0c;网络的运算和数据管理能力助力各个行业高速发展&#xff0c;但同样带来了一些网络安全隐患&#xff0c;网络攻击、数据窃取、敏感信息泄露等问题。为此&#xff0c;我国出台了系列政策来全面提升银各行业系统网络安全整体防护水平&#xff0c;其中“…

electron+vue3全家桶+vite项目搭建【25】使用electron-updater自动更新应用

文章目录 引入实现效果实现步骤引入依赖配置electron-buidler文件封装版本升级工具类主进程调用版本更新校验渲染进程封装方法调用 测试版本更新 引入 demo项目地址 electron-updater官网 我们不可能每次发布新的版本都让用户去手动下载安装最新的包&#xff0c;而是应用可以…

数据库与数据仓库的区别及关系

数据库与数据仓库的区别及关系 数据库数据仓库异同差异联系例子 数据库 数据库是结构化信息或数据的有序集合&#xff0c;一般以电子形式存储在计算机系统中。通常由数据库管理系统 (DBMS) 来控制。它是一个长期存储在计算机内的、有组织的、可共享的、统一管理的大量数据的集…

python 合并多个excel文件

使用 openpyxl 思路&#xff1a; 读取n个excel的文件&#xff0c;存储在一个二维数组中&#xff0c;注意需要转置。将二维数组的数据写入excel。 安装软件&#xff1a; pip install openpyxl源代码&#xff1a; import os import openpyxl # 将n个excel文件数据合并到一个…

模拟实现消息队列项目(系列4) -- 服务器模块(内存管理)

目录 前言 1. 创建MemoryDataCenter 2. 封装Exchange 和 Queue方法 3. 封装Binding操作 4. 封装Message操作 4.1 封装消息中心集合messageMap 4.2 封装消息与队列的关系集合queueMessageMap的操作 5. 封装未确认消息集合waitMessage的操作 6. 从硬盘中恢复数据到内存中 7. Memo…

Leetcode 每日一题 - 删除有序数组中的重复项题 #算法 #Java

1.1 题目 给你一个 升序排列 的数组 nums &#xff0c;请你 原地 删除重复出现的元素&#xff0c;使每个元素 只出现一次 &#xff0c;返回删除后数组的新长度。元素的 相对顺序 应该保持 一致 。然后返回 nums 中唯一元素的个数。 考虑 nums 的唯一元素的数量为 k &#xff…

行业追踪,2023-08-07

自动复盘 2023-08-07 凡所有相&#xff0c;皆是虚妄。若见诸相非相&#xff0c;即见如来。 k 线图是最好的老师&#xff0c;每天持续发布板块的rps排名&#xff0c;追踪板块&#xff0c;板块来开仓&#xff0c;板块去清仓&#xff0c;丢弃自以为是的想法&#xff0c;板块去留让…

虹科分享 | 新时代“救命神器”:看AR眼镜如何应用于紧急救险场景

从工业时代到如今迎来的“体验时代”&#xff0c;体验即内容&#xff0c;5G、AI、空间计算技术的突破&#xff0c;为各行各业创建了丰富的内容体验模式&#xff0c;让人们能够听之、触之、与之交互。AR是体验时代最具潜力的新技术&#xff0c;在“应急”场景中更是成为了我们在…

JSP实训项目设计报告—MVC简易购物商城

JSP实训项目设计报告—MVC简易购物商城 文章目录 JSP实训项目设计报告—MVC简易购物商城设计目的设计要求设计思路系统要求单点登录模块商品展示模块购物车展示模块 概要设计Model层View层Controller层 详细设计Model层View层登录界面系统主界面 Controller层 系统运行效果项目…

云计算——ACA学习 云计算概述

作者简介&#xff1a;一名云计算网络运维人员、每天分享网络与运维的技术与干货。 座右铭&#xff1a;低头赶路&#xff0c;敬事如仪 个人主页&#xff1a;网络豆的主页​​​​​ 目录 写在前面 上章回顾 本章简介 本章目标 一.云计算产生背景 1.信息时代的重点变革…

【VUE】前端实现防篡改的水印

效果 水印的作用 图片加水印的操作一般是由后端来完成&#xff0c;有些站点保护的知识产权的类型可能比较多&#xff0c;不仅仅是图片&#xff0c;可能还有视频、文字等等&#xff0c;对于不同类型的对象添加水印后端操作比较复杂&#xff0c;所有有些站点逐步的让前端去进行水…

认识所有权

专栏简介&#xff1a;本专栏作为Rust语言的入门级的文章&#xff0c;目的是为了分享关于Rust语言的编程技巧和知识。对于Rust语言&#xff0c;虽然历史没有C、和python历史悠远&#xff0c;但是它的优点可以说是非常的多&#xff0c;既继承了C运行速度&#xff0c;还拥有了Java…

前沿分享-鱼形机器人

可能并不太前沿了&#xff0c;是21年底的新闻了&#xff0c;但是看见了就顺便发一下吧。 大概就是&#xff0c;通过在pH响应型水凝胶中编码不同的膨胀速率而构建了一种环境适应型变形微机器人,让微型机器人直接向癌细胞输送药物从而减轻药物带来副作用。 技术原理是&#xff0c…

拦截器对接口细粒度权限校验

文章目录 一、逻辑分析二、校验规则1.规则类型2.规则划分3.规则配置信息4.规则案例说明5.规则加载 三、拦截器定义1.自定义拦截器2.注册拦截器 四、获取请求参数1.获取get提交方式参数2.获取post提交方式参数&#xff08;1&#xff09;定义RequestWrapper类&#xff08;2&#…

Flink正常消费一段时间后,大量反压,看着像卡住了,但又没有报错。

文章目录 前言一、原因分析二、解决方案 前言 前面我也有提到&#xff0c;发现flink运行一段时间后&#xff0c;不再继续消费的问题。这个问题困扰了我非常久&#xff0c;一开始也很迷茫。又因为比较忙&#xff0c;所以一直没有时间能够去寻找答案&#xff0c;只是通过每天重启…

IDEA中maven项目失效,pom.xml文件橙色/橘色

IDEA中maven项目失效&#xff0c;pom.xml文件橙色/橘色 IDEA中Maven项目失效 IDEA中创建的maven项目中的文件夹都变成普通格式&#xff0c;pom.xml变成橙色 右键点击橙色的pom.xml文件&#xff0c;选择add as maven project maven项目开始重新导入相应依赖&#xff0c;恢复…