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

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

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

【问题描述】

在郊区有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

 


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

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

分享给朋友:

相关文章

【题解】开花

【题解】开花

【题目描述】小A所在的学校又迎来了一年一度的开花活动,有 n 名学生被评为文学优秀奖,m 名学生被评为体育优秀奖。现已知两个奖项获奖同学的编号,每个同学都有唯一的编号。只有同时被评为文学优秀奖和体育优...

【题解】区间数位个数

2.区间数位个数(digit.cpp)【描述】给定整数n和整数k,求出1~n中所有数的每一位数字中,出现数字k的次数。【输入】第一行是两个个整数n和k【输出】一个整数表示答案。【样例输入输出】ligh...

【动态规划】完全背包

【题目描述】设有n种物品,每种物品有一个重量及一个价值。但每种物品的数量是无限的,同时有一个背包,最大载重量为m,今从n种物品中选取若干件(同一种物品可以多次选取),使其重量的和小于等于m,而价值的和...

【题解】循环比赛日程表

【题解】循环比赛日程表

【题目描述】设有N个选手进行循环比赛,其中N=2M,要求每名选手要与其他N-1名选手都赛一次,每名选手每天比赛一次,循环赛共进行N-1天,要求每天没有选手轮空。【输入描述】输入:M。【输出描述】输出:...

【算法】滑动窗口2—窗口大小可变

【算法】滑动窗口2—窗口大小可变

对于滑动窗口第二类:窗口大小可变类型 图解如下,类似双指针算法。【解题思想】1、字符串 S 中使用双指针的左右指针技巧,初始化 left = right = 0,把索引的...

【题解】自动晾衣机

【题目描述】有一个环形可以晾衣服的衣架,有若干个夹子组成,它可以晾不同长度的衣服(占用多个夹子),并且每两件衣服中间要有一个空夹子作为空位,下面需要依次晾干几件长度不一的衣服,请你给出某个夹子的使用情...