Telephone Lines

Telephone Lines
简化一下题意,这题是在无向图上求出一条从1N的路径,使路径上第K+1大的边权尽量小。
这样的话我们可以发掘这题的金额是有二分性的,在合法的金额里面一定包含着最优金额,这样子我们就可以二分出最优金额进行求解,跑一下SPFA,金额大于mid的边边权为1,其他为0,最后判断一下d[ed]是否大于k就好,大于就是代表我现在金额不能完全修完前k条路径,然这题就解决了

发表评论

电子邮件地址不会被公开。 必填项已用*标注