第一类边应该是$i \rightarrow i-1$吧
by Rhodoks @ 2021-04-05 09:25:29
@[Rhodoks](/user/56267) 对,就是先将ai从小到大重新排序然后重新标号，然后对于每个i，从ai往ai-1连一条边，权重为0，然后每一个i二分找到一个最大的j，使得aj-ai-ci <= 0，然后从ai往这个aj连一条边，然后从ai往aj+1连一条边，j就是上面那个j，然后官方题解说这样建图就一定包含了最短路的最优解所需要的所有边。我不太清楚为啥，不知道咋证明:(
by Isaachsq @ 2021-04-05 14:28:22
考虑原图的边$i \rightarrow k$,若$k \leq j$ 则走$i \rightarrow j \rightarrow k$这条路花费总是$0$。体现在新图上就是先走到$j$然后走$i \rightarrow i-1$的边回到$k$,这里是等价的。
然后就是$k>j$的情况了，这里直接走$i \rightarrow k$ 永远比 $i \rightarrow j+1 \rightarrow k$要来得劣，因为$\max(0,a_k-a_i-c_i) \geq \max(0,a_{j+1}-a_i-c_i)+\max(0,a_k-a_{j+1}-c_{j+1})$，证明如下：
已知
$$a_{j+1} > a_i+c_i$$
令
$$A=a_{j+1}-a_i-c_i,B=a_k-a_{j+1}$$
$$A > 0,B \geq 0$$
即证
$$\max(0,A+B) \geq \max(0,A) + \max(0,B-c_{j+1})$$
即证
$$A+B \geq A+\max(0,B-c_{j+1})$$
即证
$$B \geq \max(0,B-c_{j+1})$$
显然成立。
由此如果要从$i$出发到达$k>j$，最短路之一必然经过$j+1$。
综上所述，必然存在某个原图的最短路出现在新图里。
by Rhodoks @ 2021-04-05 15:41:57
@[Rhodoks](/user/56267) 懂了，感谢！!
by Isaachsq @ 2021-04-06 12:18:54