首页 > 代码库 > 双参数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带队列优化类似于背包问题的递推
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。