P11744 Dynamic TSP Problem

A 国有 $n$ 个城市被 $n-1$ 条道路连接！这 $n$ 座城市从 $1$ 至 $n$ 编号，其中第 $i$ 座城市有三个值 $A_i$、$B_i$ 以及 $C_i$ 分别表示该城市的繁荣度、利润额和销售额。 你作为一个流浪商人，想要进行环游 A 国的 $m$ 次旅行。第 $i$ 次旅行可以描述为：以 $X$ 元的资金从城市 $S_i$ 以最短距离走到城市 $T_i$，且最终资本需要大于等于 $Y_i$，还有一个参数 $K_i$。你一路破产，一路贸易，一路生花。 * 一路破产：你需要最开始携带 $X$ 元的资金，从城市 $S_i$ 开始出发。 * 一路贸易：**你在途经的所有城市都需要进行贸易，包括出发城市和结束城市。** 假设你刚来到城市 $i$ 拥有资金 $w$ 元，若资本 $w$ 不小于该城市的繁荣度 $A_i$，那么你可以在此获利 $B_i$。否则你会消耗 $C_i$ 元的资金。路途中资金可以小于 $0$。 * 一路生花：抵达城市 $T_i$ 并在城市 $T_i$ 完成贸易后，你希望最后至少有 $Y_i$ 元的资金，且在路途中至少完成 $K_i$ 次获利（即至少有 $K_i$ 个城市满足当前资本不小于该城市的繁荣度 $A_i$）。$Y_i$ 可以小于 $X$，因为你深知破产无关紧要，绕远的路，总有风景。 你需计算 $X$ 的最小值，使得每次旅行都以 $X$ 元资金出发，且最后都至少有 $Y_i$ 元的剩余且获利至少 $K_i$ 次。保证 $K_i$ 小于等于路径长度。

无

无

**【数据规模与约定】** **本题开启子任务捆绑测试**。本题自动开启 O2 优化。 * Subtask 1（10 pts）：$n\leq 100$，$m\leq 100$。 * Subtask 2（25 pts）：$n\leq 500$，$m\leq 3000$。 * Subtask 3（10 pts）：$A_i=B_i$，$C_i=0$。 * Subtask 4（10 pts）：$B_i=0$。 * Subtask 5（10 pts）：$C_i=0$。 * Subtask 6（10 pts）：A 国的道路是一条链。 * Subtask 7（25 pts）：$n\leq 500$，$m\leq 2\times 10^5$。 对于所有测试点满足 $n\leq 500$，$m\leq 2\times 10^5$，$0\leq A_i,B_i,C_i\leq 2\times 10^{14}$，$S_i\not= T_i$，$1\leq K_i\leq n$，$1\leq Y_i\leq 10^{17}$。