T 城是一个旅游城市,具有 nnn 个景点和 mmm 条道路,所有景点编号为 1,2,...,n1,2,...,n1,2,...,n。每条道路连接这 nnn 个景区中的某两个景区,道路是单向通行的。每条道路都有一个长度。为了方便旅游,每个景点都有一个加油站。第 iii 个景点的加油站的费用为 pip_ipi,加油量为 cic_ici。若汽车在第 iii 个景点加油,则需要花费 pip_ipi 元钱,之后车的油量将被加至油量上限与 cic_ici 中的较小值。不过如果加油前汽车油量已经不小于 cic_ici,则不能在该景点加油。小 C 准备来到 T 城旅游。他的汽车油量上限为 CCC。旅游开始时,汽车的油量为 000。在旅游过程中:1、当汽车油量大于 000 时,汽车可以沿从当前景区出发的任意一条道路到达另一个景点(不能只走道路的一部分),汽车油量将减少 111;2、当汽车在景点 iii 且当前油量小于 cic_ici 时,汽车可以在当前景点加油,加油需花费 pip_ipi 元钱,这样汽车油量将变为 min{ci,C}\min{c_i,C}min{ci,C}。一次旅游的总花费等于每次加油的花费之和,旅游的总路程等于每次经过道路的长度之和。注意多次在同一景点加油,费用也要计算多次,同样地,多次经过同一条道路,路程也要计算多次。小 C 计划旅游 TTT 次,每次旅游前,小 C 都指定了该次旅游的起点和目标路程。由于行程不同,每次出发前带的钱也不同。为了省钱,小 C 需要在旅游前先规划好旅游路线(包括旅游的路径和加油的方案),使得从起点出发,按照该旅游路线旅游结束后总路程不小于目标路程,且剩下的钱尽可能多。请你规划最优旅游路线,计算这 TTT 次旅游每次结束后最多可以剩下多少钱。
solution看到 \(dis>=10^9\) 和 \(n=d\) 的最大j,所以我们要想办法预处理出这个,然后询问就可以快速回答了,\(dp[i][j]=Max(dp[k][j-p[i]]+dis[j][k])\),\(dis[i][j]\) 表示从 \(i\) 出发达到 \(j\),经过道路数不超过 \(Min(c[i],C)\) 的最长距离,可以倍增Floyd预处理出来,然后dp数组具有二分性,可以二分回答询问,但是我爆枚也过了,最坏10^9,常数太小了,哎...
#include#include#include#include#include#include#include#include#define Max(a,b) ((a)>(b)?(a):(b))#define Min(a,b) ((a)