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

【CCPC】The 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG) K

Tax

#图论 #最短路 #搜索 #暴力

题目描述

JB received his driver’s license recently. To celebrate this fact, JB decides to drive to other cities in Byteland. There are n n n cities and m m m bidirectional roads in Byteland, labeled by 1 , 2 , … , n 1,2,\dots,n 1,2,,n. JB is at the 1 1 1-st city, and he can only drive on these m m m roads. It is always possible for JB to reach every city in Byteland.

The length of each road is the same, but they are controlled by different engineering companies. For the i i i-th edge, it is controlled by the c i c_i ci-th company. If it is the k k k-th time JB drives on an edge controlled by the t t t-th company, JB needs to pay k × w t k\times w_t k×wt dollars for tax.

JB is selecting his destination city. Assume the destination is the k k k-th city, he will drive from city 1 1 1 to city k k k along the shortest path, and minimize the total tax when there are multiple shortest paths. Please write a program to help JB calculate the minimum number of dollars he needs to pay for each possible destination.

输入格式

The input contains only a single case.

The first line of the input contains two integers n n n and m m m ( 2 ≤ n ≤ 50 2 \leq n\leq 50 2n50, n − 1 ≤ m ≤ n ( n − 1 ) 2 n-1\leq m \leq \frac{n(n-1)}{2} n1m2n(n1)), denoting the number of cities and the number of bidirectional roads.

The second line contains m m m integers w 1 , w 2 , … , w m w_1,w_2,\dots,w_m w1,w2,,wm ( 1 ≤ w i ≤ 10 000 1\leq w_i\leq 10\,000 1wi10000), denoting the base tax of each company.

In the next m m m lines, the i i i-th line ( 1 ≤ i ≤ m ) (1 \le i \le m) (1im) contains three integers u i , v i u_i,v_i ui,vi and c i c_i ci ( 1 ≤ u i , v i ≤ n 1\leq u_i,v_i\leq n 1ui,vin, u i ≠ v i u_i\neq v_i ui=vi, 1 ≤ c i ≤ m 1\leq c_i\leq m 1cim), denoting denoting an bidirectional road between the u i u_i ui-th city and the v i v_i vi-th city, controlled by the c i c_i ci-th company.

It is guaranteed that there are at most one road between a pair of city, and it is always possible for JB to drive to every other city.

输出格式

Print n − 1 n-1 n1 lines, the k k k-th ( 1 ≤ k ≤ n − 1 1\leq k\leq n-1 1kn1) of which containing an integer, denoting the minimum number of dollars JB needs to pay when the destination is the ( k + 1 ) (k+1) (k+1)-th city.

样例 #1

样例输入 #1

5 6
1 8 2 1 3 9
1 2 1
2 3 2
1 4 1
3 4 6
3 5 4
4 5 1

样例输出 #1

1
9
1
3

解法

首先图只有 n ≤ 50 n\leq 50 n50,并且每条边的权值都为 1 1 1,那么我们可以使用 b f s bfs bfs或者 f l o y e d floyed floyed 求出 1 1 1号点到其他任何点的最短路径。

然后就可以枚举所有的合法的最短路径了, 由于图很小,所以直接大力 d f s dfs dfs 搜索所有可能的情况,维护最小值即可。

代码(floyed)

void solve() {int n, m;std::cin >> n >> m;std::vector<int>w(m + 1);for (int i = 1; i <= m; ++i) {std::cin >> w[i];}std::vector<std::vector<int>>dis(n + 1, std::vector<int>(n + 1, inf));std::vector<std::vector<pii>>e(n + 1);for (int i = 1; i <= m; ++i) {int u, v, c;std::cin >> u >> v >> c;e[u].push_back({ v,c });e[v].push_back({ u,c });dis[u][v] = dis[v][u] = 1;}auto floyed = [&]() {for (int i = 1; i <= n; ++i) {dis[i][i] = 0;}for (int k = 1; k <= n; ++k) {for (int i = 1; i <= n; ++i) {for (int j = 1; j <= n; ++j) {dis[i][j] = std::min(dis[i][j], dis[i][k] + dis[k][j]);}}}};floyed();std::vector<int>cnt(m + 1);std::vector<int>d(n + 1, inf);auto dfs = [&](auto&& self, int u, int sum)->void {d[u] = std::min(d[u], sum);for (auto& [v, c] : e[u]) {if (dis[1][u] + 1 == dis[1][v]) {cnt[c]++;self(self, v, sum + cnt[c] * w[c]);cnt[c]--;}}};dfs(dfs, 1, 0);for (int i = 2; i <= n; ++i) {std::cout << d[i] << "\n";}}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;//std::cin >> t;while (t--) {solve();}return 0;
}

代码(bfs)

 
void solve() {int n,m;std::cin >> n>>m;std::vector<int>w(m + 1);for (int i = 1; i <= m; ++i) {std::cin >> w[i];}std::vector<std::vector<pii>>e(n + 1);for (int i = 1; i <= m; ++i) {int u, v, c;std::cin >> u >> v >> c;e[u].push_back({ v,c });e[v].push_back({ u,c });}std::vector<bool> vis(n + 1);std::vector<int>dis(n + 1);auto bfs = [&]() {std::queue<pii>q;q.push({ 1,0 }); vis[1] = 1;while (q.size()) {auto [u, d] = q.front(); q.pop();for (auto& [v, c] : e[u]) {if (vis[v]) continue;dis[v] = dis[u] + 1;q.push({ v,dis[v] });vis[v] = 1;}}};bfs();std::vector<int>cnt(m + 1);std::vector<int>d(n + 1, inf);auto dfs = [&](auto &&self ,int u,int sum)->void {d[u] = std::min(d[u], sum);for (auto& [v, c] : e[u]) {if (dis[u] + 1 == dis[v]) {cnt[c]++;self(self, v, sum + cnt[c] * w[c]);cnt[c]--;}}};dfs(dfs, 1, 0);for (int i = 2; i <= n; ++i) {std::cout << d[i] << "\n";}}signed main() {std::ios::sync_with_stdio(0);std::cin.tie(0);std::cout.tie(0);int t = 1;//std::cin >> t;while (t--) {solve();}return 0;
}

相关文章:

【CCPC】The 2021 CCPC Guilin Onsite (XXII Open Cup, Grand Prix of EDG) K

Tax #图论 #最短路 #搜索 #暴力 题目描述 JB received his driver’s license recently. To celebrate this fact, JB decides to drive to other cities in Byteland. There are n n n cities and m m m bidirectional roads in Byteland, labeled by 1 , 2 , … , n 1,…...

selenium的实际使用

1.标签页的切换 #获取当前所有的窗口 curdriver.window_handles #根据窗口索引进行切换 driver.switch_to.window(cur[1]) from selenium import webdriverimport timedriver webdriver.Chrome()driver.get(http://www.baidu.com)time.sleep(1)eledriver.find_element_by…...

OpenShift 4 - 云原生备份容灾 - Velero 和 OADP 基础篇

《OpenShift 4.x HOL教程汇总》 说明&#xff1a; 本文主要说明能够云原生备份容灾的开源项目 Velero 及其红帽扩展项目 OADP 的概念和架构篇。操作篇见《OpenShift 4 - 使用 OADP 对容器应用进行备份和恢复&#xff08;附视频&#xff09; 》 Velero 和 OADP 包含的功能和模…...

javaWeb项目-Springboot+vue-校园论坛系统功能介绍

本项目源码&#xff08;点击下方链接下载&#xff09;&#xff1a;java-springbootvue-xx学校校园论坛信息系统实现源码(项目源码-说明文档)资源-CSDN文库 项目关键技术 开发工具&#xff1a;IDEA 、Eclipse 编程语言: Java 数据库: MySQL5.7 框架&#xff1a;ssm、Springboot…...

centors7升级GLIBC2.18

错误来源&#xff1a;找不到GLIBC2.18&#xff0c;因为glibc的版本是2.17 网上大多教程方法&#xff0c;反正我是行不通&#xff1a; 方法1&#xff1a;更新源&#xff0c;然后使用yum安装更新 方法2&#xff1a;下载源码&#xff0c;configrue&#xff0c;make执行 wget h…...

基于深度学习的异常检测

基于深度学习的异常检测是一项重要的研究领域&#xff0c;主要用于识别数据中的异常样本或行为。异常检测广泛应用于多个领域&#xff0c;如网络安全、金融欺诈检测、工业设备预测性维护、医疗诊断等。传统的异常检测方法通常依赖于统计分析或规则&#xff0c;但随着数据复杂性…...

深入理解 SQL 中的高级数据处理特性:约束、索引和触发器

在 SQL&#xff08;Structured Query Language&#xff09;中&#xff0c;除了基本的查询、插入、更新和删除操作外&#xff0c;还有一些高级的数据处理特性&#xff0c;它们对于确保数据的完整性、提高查询性能以及实现自动化的数据处理起着至关重要的作用。这些特性包括约束、…...

IC验证面试中常问知识点总结(七)附带详细回答!!!

15、 TLM通信 15.1 实现两个组件之间的通信有哪几种方法?分别什么特点? 最简单的方法就是使用全局变量,在monitor里对此全局变量进行赋值,在scoreboard里监测此全局变量值的改变。这种方法简单、直接,不过要避免使用全局变量,滥用全局变量只会造成灾难性的后果。 稍微复…...

【前端】如何制作一个自己的网页(8)

以下内容接上文。 CSS的出现&#xff0c;使得网页的样式与内容分离开来。 HTML负责网页中有哪些内容&#xff0c;CSS负责以哪种样式来展现这些内容。因此&#xff0c;CSS必须和HTML协同工作&#xff0c;那么如何在HTML中引用CSS呢&#xff1f; CSS的引用方式有三种&#xff1…...

Java之模块化详解

Java模块化&#xff0c;作为Java 9引入的一项重大特性&#xff0c;通过Java Platform Module System (JPMS) 实现&#xff0c;为Java开发者提供了更高级别的封装和依赖管理机制。这一特性旨在解决Java应用的封装性、可维护性和性能问题&#xff0c;使得开发者能够构建更加结构化…...

HTB:Knife[WriteUP]

目录 连接至HTB服务器并启动靶机 1.How many TCP ports are open on Knife? 2.What version of PHP is running on the webserver? 并没有我们需要的信息&#xff0c;接着使用浏览器访问靶机80端口 尝试使用ffuf对靶机Web进行一下目录FUZZ 使用curl访问该文件获取HTTP头…...

MOE论文详解(4)-GLaM

2022年google在GShard之后发表另一篇跟MoE相关的paper, 论文名为GLaM (Generalist Language Model), 最大的GLaM模型有1.2 trillion参数, 比GPT-3大7倍, 但成本只有GPT-3的1/3, 同时效果也超过GPT-3. 以下是两者的对比: 跟之前模型对比如下, 跟GShard和Switch-C相比, GLaM是第一…...

LeetCode322:零钱兑换

题目链接&#xff1a;322. 零钱兑换 - 力扣&#xff08;LeetCode&#xff09; 代码如下 class Solution { public:int coinChange(vector<int>& coins, int amount) {vector<int> dp(amount 1, INT_MAX);dp[0] 0;for(int i 0; i < coins.size(); i){fo…...

速盾:高防 cdn 提供 cc 防护?

在当今网络环境中&#xff0c;网站面临着各种安全威胁&#xff0c;其中 CC&#xff08;Challenge Collapsar&#xff09;攻击是一种常见的分布式拒绝服务攻击方式。高防 CDN&#xff08;Content Delivery Network&#xff0c;内容分发网络&#xff09;作为一种有效的网络安全防…...

【大数据应用开发】2023年全国职业院校技能大赛赛题第10套

如有需要备赛资料和远程培训,可私博主,详细了解 目录 任务A:大数据平台搭建(容器环境)(15分) 任务B:离线数据处理(25分) 任务C:数据挖掘(10分) 任务D:数据采集与实时计算(20分) 任务E:数据可视化(15分) 任务F:综合分析(10分) 任务A:大数据平台搭…...

【源码部署】解决SpringBoot无法加载yml文件配置,总是使用8080端口方案

打开idea&#xff0c;file ->Project Structure 找到Modules &#xff0c;在右侧找到resource目录&#xff0c;是否指定了resource&#xff0c;点击对应文件夹会有提示...

2010年国赛高教杯数学建模B题上海世博会影响力的定量评估解题全过程文档及程序

2010年国赛高教杯数学建模 B题 上海世博会影响力的定量评估 2010年上海世博会是首次在中国举办的世界博览会。从1851年伦敦的“万国工业博览会”开始&#xff0c;世博会正日益成为各国人民交流历史文化、展示科技成果、体现合作精神、展望未来发展等的重要舞台。请你们选择感兴…...

使用nginx配置静态页面展示

文章目录 前言正文安装nginx配置 前言 目前有一系列html文件&#xff0c;比如sphinx通过make html输出的文件&#xff0c;需要通过ip远程访问&#xff0c;这就需要ngnix 主要内容参考&#xff1a;https://blog.csdn.net/qq_32460819/article/details/121131062 主要针对在do…...

[IOI2018] werewolf 狼人(Kruskal重构树 + 主席树)

https://www.luogu.com.cn/problem/P4899 首先&#xff0c;我们肯定要建两棵Kruskal重构树的&#xff0c;然后判两棵子树是否有相同编号节点 这是个经典问题&#xff0c;我们首先可以拍成dfs序&#xff0c;然后映射过去&#xff0c;然后相当于是判断一个区间是否有 [ l , r …...

snmpgetnext使用说明

1.snmpgetnext介绍 snmpgetnext命令是用来获取下一个节点的OID的值。 2.snmpgetnext安装 1.snmpgetnext安装 命令: yum -y install net-snmp net-snmp-utils [root@logstash ~]# yum -y install net-snmp net-snmp-utils Loaded plugins: fastestmirror Loading mirror …...

linux之kylin系统nginx的安装

一、nginx的作用 1.可做高性能的web服务器 直接处理静态资源&#xff08;HTML/CSS/图片等&#xff09;&#xff0c;响应速度远超传统服务器类似apache支持高并发连接 2.反向代理服务器 隐藏后端服务器IP地址&#xff0c;提高安全性 3.负载均衡服务器 支持多种策略分发流量…...

脑机新手指南(八):OpenBCI_GUI:从环境搭建到数据可视化(下)

一、数据处理与分析实战 &#xff08;一&#xff09;实时滤波与参数调整 基础滤波操作 60Hz 工频滤波&#xff1a;勾选界面右侧 “60Hz” 复选框&#xff0c;可有效抑制电网干扰&#xff08;适用于北美地区&#xff0c;欧洲用户可调整为 50Hz&#xff09;。 平滑处理&…...

Java如何权衡是使用无序的数组还是有序的数组

在 Java 中,选择有序数组还是无序数组取决于具体场景的性能需求与操作特点。以下是关键权衡因素及决策指南: ⚖️ 核心权衡维度 维度有序数组无序数组查询性能二分查找 O(log n) ✅线性扫描 O(n) ❌插入/删除需移位维护顺序 O(n) ❌直接操作尾部 O(1) ✅内存开销与无序数组相…...

最新SpringBoot+SpringCloud+Nacos微服务框架分享

文章目录 前言一、服务规划二、架构核心1.cloud的pom2.gateway的异常handler3.gateway的filter4、admin的pom5、admin的登录核心 三、code-helper分享总结 前言 最近有个活蛮赶的&#xff0c;根据Excel列的需求预估的工时直接打骨折&#xff0c;不要问我为什么&#xff0c;主要…...

Java-41 深入浅出 Spring - 声明式事务的支持 事务配置 XML模式 XML+注解模式

点一下关注吧&#xff01;&#xff01;&#xff01;非常感谢&#xff01;&#xff01;持续更新&#xff01;&#xff01;&#xff01; &#x1f680; AI篇持续更新中&#xff01;&#xff08;长期更新&#xff09; 目前2025年06月05日更新到&#xff1a; AI炼丹日志-28 - Aud…...

华为云Flexus+DeepSeek征文|DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建

华为云FlexusDeepSeek征文&#xff5c;DeepSeek-V3/R1 商用服务开通全流程与本地部署搭建 前言 如今大模型其性能出色&#xff0c;华为云 ModelArts Studio_MaaS大模型即服务平台华为云内置了大模型&#xff0c;能助力我们轻松驾驭 DeepSeek-V3/R1&#xff0c;本文中将分享如何…...

HDFS分布式存储 zookeeper

hadoop介绍 狭义上hadoop是指apache的一款开源软件 用java语言实现开源框架&#xff0c;允许使用简单的变成模型跨计算机对大型集群进行分布式处理&#xff08;1.海量的数据存储 2.海量数据的计算&#xff09;Hadoop核心组件 hdfs&#xff08;分布式文件存储系统&#xff09;&a…...

JVM虚拟机:内存结构、垃圾回收、性能优化

1、JVM虚拟机的简介 Java 虚拟机(Java Virtual Machine 简称:JVM)是运行所有 Java 程序的抽象计算机,是 Java 语言的运行环境,实现了 Java 程序的跨平台特性。JVM 屏蔽了与具体操作系统平台相关的信息,使得 Java 程序只需生成在 JVM 上运行的目标代码(字节码),就可以…...

【Go语言基础【12】】指针:声明、取地址、解引用

文章目录 零、概述&#xff1a;指针 vs. 引用&#xff08;类比其他语言&#xff09;一、指针基础概念二、指针声明与初始化三、指针操作符1. &&#xff1a;取地址&#xff08;拿到内存地址&#xff09;2. *&#xff1a;解引用&#xff08;拿到值&#xff09; 四、空指针&am…...

【电力电子】基于STM32F103C8T6单片机双极性SPWM逆变(硬件篇)

本项目是基于 STM32F103C8T6 微控制器的 SPWM(正弦脉宽调制)电源模块,能够生成可调频率和幅值的正弦波交流电源输出。该项目适用于逆变器、UPS电源、变频器等应用场景。 供电电源 输入电压采集 上图为本设计的电源电路,图中 D1 为二极管, 其目的是防止正负极电源反接, …...