解题思路
选定一条从 0 到 c−1 的路径,要么整条都不升级,要么恰好升级 t 条边(带宽变为 2 倍),最大化路径瓶颈。
- 这是带额外状态的最宽路。设 f[u][used] 表示走到城市 u、路上恰好升级了 used 条边时,能得到的最大瓶颈。
- 起点还没有边,f[0][0] 视为正无穷。用最大堆每次弹出当前瓶颈最大的状态。
- 从 (u,used) 走边 (u,v) 带宽 w:不升级则新瓶颈为 min(当前,w),更新 f[v][used];若 used<t,升级则新瓶颈为 min(当前,2w),更新 f[v][used+1]。
- 答案取 f[c−1][0] 与 f[c−1][t] 的较大者:对应「整条不升级」和「恰好升级 t 条」。中间次数 1,…,t−1 不合法。
- 若两个值都是 −1,说明 0 到不了 c−1,输出 −1。