Telephone Lines_牛客博客

图片说明

思路：
如果 $1$ 号点到 $n$ 号点是连通的，那么一定可以完成，反之一定不能完成，输出-1；

解法一：分层图最短路

图中的每个节点不仅限于“整数编号”，可以扩展到二维，用二元组 $(x,p)$ 代表一个节点，表示该点的编号以及第几层，显然在同层移动需要支出费用，向高层移动不需要支出费用。从 $(x,p)$ 到 $(y,p)$ 有长度为 $z$ 的边，表示端点为 $x,y$ 的电缆需要付费；从 $(x,p)$ 到 $(y,p+1)$ 有长度为 $0$ 的边，表示端点为 $x,y$ 的电缆是免费的。
然后很容易想到用动态规划来解， $dp[x][p]$ 表示从 $1$ 号基站到基站x，途中已经指定了 $p$ 条免费的电缆时的进过路径上最贵的花费最小是多少。 $dp[x][p]$ 就是二元组 $(x,p)$ 的值，然后沿着边对应的状态转移。显然这个状态转移是有后效性的。为了解决后效性，可以利用迭代思想、借助 $SPAFA$ 算法，直至所有状态有所收敛。

MyCode:

解法二：二分答案，(循环)双端队列

本题答案显然具有单调性，支付的钱更多，一定可以完工。于是我们可以二分答案，把问题转化为是否存在一种合法升级方法，使花费不超过 $mid$ ， $mid$ 一定会不断趋近 $ans$ ，直到等于 $ans$ 。
判定时可以根据题目要求，把升级价格大于 $mid$ 的电缆长度视为 $1$ ，不超过 $mid$ 的视为 $0$ ，然后求 $1$ 到n的 $0/1$ 最短路即可。

本题求 $0/1$ 最短路时，因为是有后效性的，所以一个点可能会多次入队、出队。注意最小花费可能是 $0$ .

MyCode: