首页 > 代码库 > 双参数Bellman-ford带队列优化类似于背包问题的递推

双参数Bellman-ford带队列优化类似于背包问题的递推

为方便起见,将Bellman-ford队列优化称为SPFA,= =

抓住 ZMF (ZMF.pas/c/cpp)

题目描述

话说这又是一个伸手不见五指的夜晚,为了机房的电子竞技事业永远孜孜不倦的 ZMF 小朋友躲在一个阴暗的角落(毫无疑问又搞起了)。当然,另一个神龙见首不见尾的黑影也偷偷地出现在了后门……此时我们敬爱的 MR.LI 开始为如何抓住 ZMF 发愁了:为了捉住 ZMF,经过其他人的座位是不可避免的,其他人也会发出或大或小的响声,而一旦响声之和超过了一定的值,把游戏当成作业的 ZMF 便会发现这一切,从而销毁作案现场(例如重新启动之类)。现在的你需要编写一个程序,判断出 MR.LI在不惊动 ZMF 的前提下,到达 ZMF 座位的最短路线。(求问被黑的ZMF是谁呢?>_<)

输入格式

第一行有两个数 N 和 P,分别表示座位个数(包括 MR.LI,MR.LI 的编号为 1,ZMF 的编号为 N) 和 ZMF 的警觉程度(即允许响声和的最大值)。N<=50,P<=50

接下来的 N 行,每行有 N 个数,第 I 行第 J 个数表示从 I 走到 J 的路程。0 表示不可到达。

最后有 N 行,每行 N 个数,第 I 行第 J 个数表示从 I 走到 J 所发出的响声。

输出格式

一个数 T,表示最短路径的长度。如果抓不到,则输出“what a pity”。

测试数据

输入____________________5 50 100 100 1 10 0 0 0 1000 0 0 0 00 0 0 0 00 0 0 0 00 1 1 10 1000 0 0 0 20 0 0 0 00 0 0 0 0输出____________________200

这是一道例题。

首先,我们可以发现,是一个较为传统的最短路题。只是多了限制条件,响声和不能大于某个数。
那么可以将每条边的响声值设为重量,这就是一个背包问题了。但是要同时求出最短路(仁义厚道的是无需输出方案),怎么办呢?

注意到DP背包问题是DP的形式,F[余下总重]=max{F[余下总重],F[余下总重-w[当前节点]]+v[当前节点]}

由于是蒟蒻,以前没做过类似的题目= =,然后就SB了。受到WJZ大神的启发。。

而SPFA的松弛, 和背包问题很类似,F[i]=min{F[i],F[j]+P[j][i]}我们可以将它看成是DP。那么让我们加一维,变成这样:

F[i][j]=min{F[i][j],F[k][j-w[k][i]]+P[k][i]}

这样可以保证答案是由可行的路径松弛而来的,由于j是有范围的。

最后膜拜WJZ大神!今年一定是要Au的节奏!>_< [//如果没有Au一定是数据错了恩

双参数Bellman-ford带队列优化类似于背包问题的递推