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

AcWing算法提高课-3.1.2信使

宣传一下算法提高课整理 <—

CSDN个人主页:更好的阅读体验 <—

csdn

题目传送门点这里

题目描述

战争时期,前线有 nnn 个哨所,每个哨所可能会与其他若干个哨所之间有通信联系。

信使负责在哨所之间传递信息,当然,这是要花费一定时间的(以天为单位)。

指挥部设在第一个哨所。

当指挥部下达一个命令后,指挥部就派出若干个信使向与指挥部相连的哨所送信。

当一个哨所接到信后,这个哨所内的信使们也以同样的方式向其他哨所送信。信在一个哨所内停留的时间可以忽略不计。

直至所有 nnn 个哨所全部接到命令后,送信才算成功。

因为准备充足,每个哨所内都安排了足够的信使(如果一个哨所与其他 k 个哨所有通信联系的话,这个哨所内至少会配备 kkk 个信使)。

现在总指挥请你编一个程序,计算出完成整个送信过程最短需要多少时间。

输入格式

111 行有两个整数 nnnmmm,中间用 111 个空格隔开,分别表示有 nnn 个哨所和 mmm 条通信线路。

222m+1m+1m+1 行:每行三个整数 i、j、ki、j、kijk,中间用 111 个空格隔开,表示第 iii 个和第 jjj 个哨所之间存在 双向 通信线路,且这条线路要花费 kkk 天。

输出格式

一个整数,表示完成整个送信过程的最短时间。

如果不是所有的哨所都能收到信,就输出-1

数据范围

1≤n≤100,1≤n≤100,1n100,
1≤m≤200,1≤m≤200,1m200,
1≤k≤10001≤k≤10001k1000

样例输入

4 4
1 2 4
2 3 7
2 4 1
3 4 6

样例输出

11

题目化简:

给定一个 nnn 个点 mmm 条边的无向图,求编号为1的点与其他点之间最短距离的最大值。

思路

这道题因为数据范围极小,为了节约代码长度,可以采用Floyd算法。

在求出任意两点间最短距离之后,遍历dist[1][i],求出最大值。

Dijkstra算法与Floyd类似,代码部分也给出了朴素Dijkstra和堆优化Dijkstra的代码。

算法时间复杂度

如果采用Floyd算法,那么时间复杂度是O(n3)O(n^3)O(n3)

朴素Dijkstra算法:O(n2)O(n^2)O(n2), 但是代码较长;

堆优化Dijkstra算法:O(mlog⁡n)O(m \log n)O(mlogn),同样的代码较长

AC Code

C++(Floyd)C++ (Floyd)C++(Floyd)

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110, inf = 1e9;int n, m;
int d[N][N];void init()
{for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )if (i == j) d[i][j] = 0;else d[i][j] = inf;
}void floyd()
{for (int k = 1; k <= n; k ++ )for (int i = 1; i <= n; i ++ )for (int j = 1; j <= n; j ++ )d[i][j] = min(d[i][j], d[i][k] + d[k][j]);
}int main()
{cin >> n >> m;init();while (m -- ){int a, b, c;cin >> a >> b >> c;d[a][b] = min(d[a][b], c);d[b][a] = min(d[b][a], c);}floyd();int res = 0;for (int i = 2; i <= n; i ++ )res = max(res, d[1][i]);if (res == inf) puts("-1");else printf("%d\n", res);return 0;
}

C++(朴素Dijkstra)C++ (朴素Dijkstra)C++(朴素Dijkstra)

#include <iostream>
#include <cstring>
#include <algorithm>using namespace std;const int N = 110;int n, m;
int g[N][N];
int dist[N];
bool st[N];int dijkstra()
{int res = 0;memset(dist, 0x3f, sizeof dist);dist[1] = 0;for (int i = 1; i <= n; i ++ ){int t = -1;for (int j = 1; j <= n; j ++ )if (!st[j] &&(t == -1 || dist[t] > dist[j]))t = j;st[t] = true;res = max(res, dist[t]);for (int j = 1; j <= n; j ++ )dist[j] = min(dist[j], dist[t] + g[t][j]);}return res == 0x3f3f3f3f ? -1 : res;
}
int main()
{memset(g, 0x3f, sizeof g);scanf("%d%d", &n, &m);while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c);g[a][b] = g[b][a] = min(g[a][b], c);}cout << dijkstra() << endl;return 0;
}

C++(堆优化Dijkstra)C++ (堆优化Dijkstra)C++(堆优化Dijkstra)

#include <iostream>
#include <cstring>
#include <algorithm>
#include <queue>#define x first
#define y secondusing namespace std;typedef pair<int, int> PII;const int N = 110, M = N << 2;int n, m;
int h[N], e[M], w[M], ne[M], idx;
int dist[N];
bool st[N];void add(int a, int b, int c)
{e[idx] = b, w[idx] = c, ne[idx] = h[a], h[a] = idx ++ ;
}
int dijkstra()
{int res = 0, cnt = 0;memset(dist, 0x3f, sizeof dist);dist[1] = 0;priority_queue<PII, vector<PII>, greater<>> heap;heap.push({0, 1});while (!heap.empty()){PII u = heap.top();heap.pop();if (st[u.y]) continue;st[u.y] = true;res = max(res, u.x);cnt ++ ;for (int i = h[u.y]; ~i; i = ne[i]){int j = e[i];if (dist[j] > dist[u.y] + w[i]){dist[j] = dist[u.y] + w[i];heap.push({dist[j], j});}}}return cnt == n ? res : -1;
}
int main()
{memset(h, -1, sizeof h);scanf("%d%d", &n, &m);while (m -- ){int a, b, c;scanf("%d%d%d", &a, &b, &c);add(a, b, c), add(b, a, c);}cout << dijkstra() << endl;return 0;
}

a

最后,如果觉得对您有帮助的话,点个赞再走吧!

相关文章:

AcWing算法提高课-3.1.2信使

宣传一下算法提高课整理 <— CSDN个人主页&#xff1a;更好的阅读体验 <— 题目传送门点这里 题目描述 战争时期&#xff0c;前线有 nnn 个哨所&#xff0c;每个哨所可能会与其他若干个哨所之间有通信联系。 信使负责在哨所之间传递信息&#xff0c;当然&#xff0c;…...

Paddle OCR Win 11下的安装和简单使用教程

Paddle OCR Win 11下的安装和简单使用教程 对于中文的识别&#xff0c;可以考虑直接使用Paddle OCR&#xff0c;识别准确率和部署都相对比较方便。 环境搭建 目前PaddlePaddle 发布到v2.4&#xff0c;先下载paddlepaddle&#xff0c;再下载paddleocr。根据自己设备操作系统进…...

杂谈:数组index问题和对象key问题

面试题一&#xff1a; var arr [1, 2, 3, 4] 问&#xff1a;arr[1] ?; arr[1] ?答&#xff1a;arr[1] 2; arr[1] 2 这里可以再分为两个问题&#xff1a; 1、数组赋值 var arr [1, 2, 3, 4]arr[1] 10; // 数字场景 arr[10] 1; // 字符串场景 arr[a] 1; // 字符串…...

三天Golang快速入门—Slice切片

三天Golang快速入门—Slice切片Slice切片切片原理切片遍历append函数操作切片append添加append追加多个切片中删除元素切片合并string和slice的联系Slice切片 切片原理 由三个部分构成&#xff0c;指针、长度、容量指针&#xff1a;指向slice第一个元素对应的数组元素的地址长…...

腾讯会议演示者视图/演讲者视图

前言 使用腾讯会议共享PPT时&#xff0c;腾讯会议支持共享用户使用演示者视图/演讲者视图&#xff0c;而会议其他成员可以看到正常的放映视图。下面以Win10系统和Office为例&#xff0c;介绍使用步骤。值得一提的是&#xff0c;该方法同时适用于单显示屏和多显示屏。 腾讯会议…...

【C++】类与对象(一)

文章目录1、面向过程和面向对象初步认识2、类的引入3、类的定义4、类的访问限定符5、类的作用域6、类的实例化7、计算类对象的大小8、this指针9、 C语言和C实现Stack的对比1、面向过程和面向对象初步认识 C语言是面向过程的&#xff0c;关注的是过程&#xff0c;分析出求解问题…...

JavaScript基本语法

本文提到的绝大多数语法都是与Java不同的语法,相同的就不会赘述了.JavaScript的三种引入方式内部js<body><script>alert(hello);</script> </body>行内js<body><div onclick"alert(hello)">这是一个div 点击一下试试</div>…...

OpenCV4.x图像处理实例-道路车辆检测(基于背景消减法)

通过背景消减进行道路车辆检测 文章目录 通过背景消减进行道路车辆检测1、车辆检测思路介绍2、BackgroundSubtractorMOG23、车辆检测实现在本文中,将介绍如何使用简单但有效的背景-前景减法方法执行车辆检测等任务。本文将使用 OpenCV 中使用背景-前景减法和轮廓检测,以及如何…...

pwnlab通关流程

pwnlab通关 关于文件包含&#xff0c;环境变量劫持的一个靶场 信息收集 靶机ip&#xff1a;192.168.112.133 开放端口 根据开放的端口信息决定从80web端口入手 目录信息 在images和upload路径存在目录遍历&#xff0c;config.php被渲染无法查看&#xff0c;upload.php需…...

面向过程与面向对象的区别与联系

目录 什么是面向过程 什么是面向对象 区别 各自的优缺点 什么是面向过程 面向过程是一种以事件为中心的编程思想&#xff0c;编程的时候把解决问题的步骤分析出来&#xff0c;然后用函数把这些步骤实现&#xff0c;在一步一步的具体步骤中再按顺序调用函数。 什么是面向对…...

主机状态(查看资源占用情况、查看网络占用情况)

1. 查看资源占用情况 【1】可以通过top命令查看cpu、内存的使用情况&#xff0c;类似windows的任务管理器 默认5s刷新一次 语法&#xff1a;top 可 Ctrl c 退出 2.磁盘信息监控 【1】使用df命令&#xff0c;查看磁盘信息占用情况 语法&#xff1a;df [ -h ] 以更加人性化…...

代码随想录算法训练营第四十一天 | 01背包问题-二维数组滚动数组,416. 分割等和子集

一、参考资料01背包问题 二维 https://programmercarl.com/%E8%83%8C%E5%8C%85%E7%90%86%E8%AE%BA%E5%9F%BA%E7%A1%8001%E8%83%8C%E5%8C%85-1.html 视频讲解&#xff1a;https://www.bilibili.com/video/BV1cg411g7Y6 01背包问题 一维 https://programmercarl.com/%E8%83%8C%E5…...

VMware NSX 4.1 发布 - 网络安全虚拟化平台

请访问原文链接&#xff1a;VMware NSX 4 - 网络安全虚拟化平台&#xff0c;查看最新版。原创作品&#xff0c;转载请保留出处。 作者主页&#xff1a;www.sysin.org VMware NSX 提供了一个敏捷式软件定义基础架构&#xff0c;用来构建云原生应用程序环境。NSX 专注于为具有异…...

计算理论 复杂度预备知识

文章目录计算理论 复杂度预备知识符号递归表达式求解通项公式主方法Akra-Bazzi 定理计算理论 复杂度预备知识 符号 f(n)o(g(n))f(n)o(g(n))f(n)o(g(n)) &#xff1a;∃c\exists c∃c &#xff0c;当 nnn 足够大时&#xff0c; f(n)<cg(n)f(n)\lt cg(n)f(n)<cg(n) &#…...

二叉树——二叉搜索树中的插入操作

二叉搜索树中的插入操作 链接 给定二叉搜索树&#xff08;BST&#xff09;的根节点 root 和要插入树中的值 value &#xff0c;将值插入二叉搜索树。 返回插入后二叉搜索树的根节点。 输入数据 保证 &#xff0c;新值和原始二叉搜索树中的任意节点值都不同。 注意&#xff0c…...

C# if break,if continue,if return的区别和使用

故事部分&#xff1a; 现在你肚子饿了&#xff0c;想要去&#xff1a; 1.吃个三菜一汤。 2.吃个蛋糕。 3.喝个奶茶。 结果&#xff0c;你吃饭的时候&#xff0c;吃到一个虫子。 你会有几种做法&#xff1f; 1.把有虫子这道菜拿走&#xff0c;继续吃下一道菜 。 2.算了&#xff…...

力扣-第二高的薪水

大家好&#xff0c;我是空空star&#xff0c;本篇带大家了解一道中等的力扣sql练习题。 文章目录前言一、题目&#xff1a;176. 第二高的薪水二、解题1.正确示范①提交SQL运行结果2.正确示范②提交SQL运行结果3.正确示范③提交SQL运行结果4.正确示范④提交SQL运行结果5.其他总结…...

I - 太阳轰炸(组合数学Cnk n固定)

2023河南省赛组队训练赛&#xff08;二&#xff09; - Virtual Judge (vjudge.net) 背景&#xff1a;阿塔尼斯&#xff0c;达拉姆的大主教&#xff0c;在艾尔又一次沦陷之后指挥着星灵的最后一艘方舟舰&#xff1a;亚顿之矛。作为艾尔星灵数千年来的智慧结晶&#xff0c;亚顿之…...

centos安装gitlab

更新系统 sudo yum -y update安装所需要的包 sudo yum -y install epel-release curl vim policycoreutils-python如果要安装并使用本地Postfix服务器发送通知&#xff0c;请安装Postfix&#xff0c;这里就不安装了&#xff1a; sudo yum -y install postfix安装后启动并启用…...

【洛谷 P1093】[NOIP2007 普及组] 奖学金 题解(结构体排序)

[NOIP2007 普及组] 奖学金 题目描述 某小学最近得到了一笔赞助&#xff0c;打算拿出其中一部分为学习成绩优秀的前 555 名学生发奖学金。期末&#xff0c;每个学生都有 333 门课的成绩:语文、数学、英语。先按总分从高到低排序&#xff0c;如果两个同学总分相同&#xff0c;再…...

定时器任务——若依源码分析

分析util包下面的工具类schedule utils&#xff1a; ScheduleUtils 是若依中用于与 Quartz 框架交互的工具类&#xff0c;封装了定时任务的 创建、更新、暂停、删除等核心逻辑。 createScheduleJob createScheduleJob 用于将任务注册到 Quartz&#xff0c;先构建任务的 JobD…...

python爬虫:Newspaper3k 的详细使用(好用的新闻网站文章抓取和解析的Python库)

更多内容请见: 爬虫和逆向教程-专栏介绍和目录 文章目录 一、Newspaper3k 概述1.1 Newspaper3k 介绍1.2 主要功能1.3 典型应用场景1.4 安装二、基本用法2.2 提取单篇文章的内容2.2 处理多篇文档三、高级选项3.1 自定义配置3.2 分析文章情感四、实战案例4.1 构建新闻摘要聚合器…...

Ascend NPU上适配Step-Audio模型

1 概述 1.1 简述 Step-Audio 是业界首个集语音理解与生成控制一体化的产品级开源实时语音对话系统&#xff0c;支持多语言对话&#xff08;如 中文&#xff0c;英文&#xff0c;日语&#xff09;&#xff0c;语音情感&#xff08;如 开心&#xff0c;悲伤&#xff09;&#x…...

EtherNet/IP转DeviceNet协议网关详解

一&#xff0c;设备主要功能 疆鸿智能JH-DVN-EIP本产品是自主研发的一款EtherNet/IP从站功能的通讯网关。该产品主要功能是连接DeviceNet总线和EtherNet/IP网络&#xff0c;本网关连接到EtherNet/IP总线中做为从站使用&#xff0c;连接到DeviceNet总线中做为从站使用。 在自动…...

JUC笔记(上)-复习 涉及死锁 volatile synchronized CAS 原子操作

一、上下文切换 即使单核CPU也可以进行多线程执行代码&#xff0c;CPU会给每个线程分配CPU时间片来实现这个机制。时间片非常短&#xff0c;所以CPU会不断地切换线程执行&#xff0c;从而让我们感觉多个线程是同时执行的。时间片一般是十几毫秒(ms)。通过时间片分配算法执行。…...

Aspose.PDF 限制绕过方案:Java 字节码技术实战分享(仅供学习)

Aspose.PDF 限制绕过方案&#xff1a;Java 字节码技术实战分享&#xff08;仅供学习&#xff09; 一、Aspose.PDF 简介二、说明&#xff08;⚠️仅供学习与研究使用&#xff09;三、技术流程总览四、准备工作1. 下载 Jar 包2. Maven 项目依赖配置 五、字节码修改实现代码&#…...

排序算法总结(C++)

目录 一、稳定性二、排序算法选择、冒泡、插入排序归并排序随机快速排序堆排序基数排序计数排序 三、总结 一、稳定性 排序算法的稳定性是指&#xff1a;同样大小的样本 **&#xff08;同样大小的数据&#xff09;**在排序之后不会改变原始的相对次序。 稳定性对基础类型对象…...

Go语言多线程问题

打印零与奇偶数&#xff08;leetcode 1116&#xff09; 方法1&#xff1a;使用互斥锁和条件变量 package mainimport ("fmt""sync" )type ZeroEvenOdd struct {n intzeroMutex sync.MutexevenMutex sync.MutexoddMutex sync.Mutexcurrent int…...

python爬虫——气象数据爬取

一、导入库与全局配置 python 运行 import json import datetime import time import requests from sqlalchemy import create_engine import csv import pandas as pd作用&#xff1a; 引入数据解析、网络请求、时间处理、数据库操作等所需库。requests&#xff1a;发送 …...

《Docker》架构

文章目录 架构模式单机架构应用数据分离架构应用服务器集群架构读写分离/主从分离架构冷热分离架构垂直分库架构微服务架构容器编排架构什么是容器&#xff0c;docker&#xff0c;镜像&#xff0c;k8s 架构模式 单机架构 单机架构其实就是应用服务器和单机服务器都部署在同一…...