信息学一本通,图论2405: 信息学奥赛一本通T1496-架设电话线题解

庄子墨 算法基础篇 53 0
想要检验自己的编程水平?来试试全网最全C++题库,让您在挑战中不断进步。
在郊区有N座通信基站,P条双向电缆,第i条电缆连接基站Ai和Bi,特别地,1号基站是通信公司的总站,N号基站位于一座农场中,现在,农场主希望对通信线路进行升级,其中升级第i条电缆需要花费Li ,一句话题意:在加权无向图上求出一条从1号结点到N号结点的路径,使路径上第K+1大的边权尽量小。

原题来自:USACO 2008 Jan. Silver 在郊区有 N 座通信基站,P 条双向电缆,第 i 条电缆连接基站 Ai和 Bi。特别地,1 号基站是通信公司的总站,N 号基站位于一座农场中。现在,农场主希望对通信线路进行升级,其中升级第 i 条电缆需要花费 Li 。 电话公司正在举行优惠活动。农场主可以指定一条从 1 号基站到 N 号基站的路径,并指定路径上不超过 K 条电缆,由电话公司免费提供升级服务。农场主只需要支付在该路径上剩余的电缆中,升级价格最贵的那条电缆的花费即可。求至少用多少钱能完成升级。 一句话题意:在加权无向图上求出一条从 1 号结点到 N 号结点的路径,使路径上第 K+1 大的边权尽量小。

信息学一本通,图论2405: 信息学奥赛一本通T1496-架设电话线题解
-第1张图片-东莞河马信息技术
(图片来源网络,侵删)

标签: 信息学一本通 图论2405: 信息学奥赛一本通T1496-架设电话线题解