当前位置:首页 > 题解目录 > 正文内容

【题解】电缆线(2019青岛市程序设计竞赛)

亿万年的星光4年前 (2021-04-16)题解目录7294

【问题描述】

在郊区有N座通信基站,P条双向电缆,第 i 条电缆连接基站 A_i 和 B_i。特别地,1号基站是通信公司的总站,N号基站位于一座农场中。现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费 L_i。

电话公司正在举行优惠活动。农场主可以指定一条从1号基站到N号基站的路径,并指定路径上不超过K条电缆,由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中,升级价格最贵的那条电缆的花费即可。

求最少用多少钱能完成升级。

【输入】

第一行,3个空格隔开正整数N,P,K。

以下P行:每行是:Ai, Bi, Li

【输出】

最少的升级花费。

line.in

line.out

5 7 1

1 2 5

3 1 4

2 4 8

3 2 3

5 2 9

3 4 7

4 5 6

4

【数据范围】

30%的数据:1 ≤ N ≤ 50,1 ≤ P ≤ 200;

100%的数据:1 ≤ N ≤ 1,000;1 ≤ P ≤ 10,000;1 ≤ Li ≤ 1,000,000;0 ≤ K < N。

【来源】

2019年青岛市程序设计竞赛试题(初中组)4T

 


扫描二维码推送至手机访问。

版权声明:本文由青少年编程知识记录发布,如需转载请注明出处。

分享给朋友:

相关文章

【题解】种花问题

【题目描述】假设有一个很长的花坛,一部分地块种植了花,另一部分却没有。可是,花不能种植在相邻的地块上,它们会争夺水源,两者都会死去。给你一个整数数组 flowerbed 表示花坛,...

【题解】黑色联通块

【题解】黑色联通块

【题目描述】输入一个n×n的黑白图像(1表示黑色,0表示白色),任务是统计其中黑色连通块的个数。如果两个黑格子有公共边或者公共顶点,就说它们属于同一个联通块。如下图所示的图形有3个联通块。【输入描述】...

八皇后2

【题目描述】会下国际象棋的人都很清楚:皇后可以在横、竖、斜线上不限步数地吃掉其他棋子。如何将8个皇后放在棋盘上(有8 × 8个方格),使它们谁也不能被吃掉!这就是著名的八皇后问题。对于某个满足要求的8...

绝对素数

【题目描述】如果一个自然数是素数,且它的数字位置经过对换后仍为素数,则称为绝对素数,例如13。试求出所有二位绝对素数。【输入描述】无【输出描述】所有二位绝对素数(由小到大,一个数一行)。【输入样例】无...

【题解】画百钱买百鸡

【题目描述】鸡翁一,值钱五,鸡母一,值钱三,鸡雏三,值钱一,百钱买百鸡。问鸡翁、鸡母、鸡雏各几何?#include<iostream> using namespace ...

【题解】真分数(2019青岛市程序设计竞赛)

【描述】真分数,指的是分子比分母小的分数,真分数的分数值小于1。给出n个正整数,任取两个数分别作为分子和分母组成真分数。求能组成多少不同值的真分数。【输入】第一行是一个正整数n。第二行是n个不同的正整...