https://www.luogu.com.cn/problem/CF1503C

下面是官方题解跑dijkstra的建图方式 不是很理解为什么这样建图就一定可以将最优解包括进来

Add the following edges:

ai→ai−1 with weight 0.

i→j with weight 0, where j is the largest index with aj−ai−ci≤0. The index j can be found with binary search.

i→j+1 with weight max(0,aj+1−ai−ci) where j is the same as before.

Every edge in this new graph corresponds to an edge in the original graph, and every edge in the original graph corresponds to a path in the new graph with at most the same cost. So the distance from a1 to an is preserved.