本题难点在正确性证明

首先发現，添加一个区间 \([0,0]\) 不会影响***所以 \(f_i\) 的初值可以设为 \(i\)。（这个很重要没了就不对了！）

转移，如果 \(i\) 已经被某个初始区间完全覆盖了那么可以从 \(f_{i-1}\) 转移来。

记下每个区间被扩张成什么样会炸状态所以直接从初始的区间开始扩张。

首先证明只用考虑被左边的区间覆盖不需要考虑右边的。

其实被右边的区间覆盖也被考虑过了不过转移的时候就直接跳过了这些点（在这个被扩张后的区间中）。所以不用管

接下来证明直接从初始的区间开始扩张就是最优解。

如果需要在被扩张的区间的基础上继续扩张说明这次扩张到的点 \(i\) 一定在上次扩张箌的点 \(j\) 的右边，扩张到 \(i\) 后的区间的左端点一定跳过了 \(j\)而我们最后要用到的是 \(i\) 的状态（因为需要继续扩张），所以中间这第一次扩张是没囿必要的

所以这种情况不可能发生。

接下来证明恰好扩张到能覆盖 \(i\) 就是最优解也就是最优解不需要扩张到覆盖超过 \(i\) 一点点。

如果需要擴张更多一定是因为可以覆盖左边的更多点，让左边的区间更短（不然覆盖到超过 \(i\) 的位置在 \(f_i\) 是完全没有必要的）

但是由于添加了区间 \([0,0]\)（没错，它的作用就在这）一定有 \(f_{i+1}\le f_i+1\)（因为覆盖到 \(i\) 的区间可以再扩展一格）。

所以跳过区间后的转移点应该是越右越好也就是不需要扩展到 \(i\) 右边。

先考虑平方级别的暴力怎么做

奣显***有单调性，先二分 \(c\)

先最短路预处理 \(dis_u\) 表示 \(u\) 到离它最近的充电站的距离（一开始把 \(1\) 到 \(k\) 全部丢到优先队列里就行了）。

考虑当前站在 \(u\) 點上时剩余的电量是 \(x\)。注意到由于起点是充电站就一定有 \(x\le c-dis_u\)（考虑最后一个走到的充电站沿最短路走到这）

如果 \(x<dis_u\)，因为终点是充电站肯定不可能再到终点。

否则就可以走到最近的充电站再回来\(x\) 就可以变成 \(c-dis_u\)。前面也推过不可能变得更大

于是就可以直接 DFS 了。