RT。蒟蒻刚学线段树优化建图，看了一眼题面打了个线段树优化建图加了个dij。通过记录。

但题解区全是单调队列加dp。感觉最短路实际也是可行的。求大佬看下该解法是否可行，如果可行想写个题解提交给管理员。

具体思路如下：

• 将 $i$ 与 $[i+1,i+k+1]$ 区间连边，边权为 $a[i]$，当然，$[i+k+1]\leq n+1$。

• 添加超级节点 $n+1$ 与 $i+k+1>n+1$ 的节点连边。 每次暴力连 $a[i]$。

因为这建边是 $O(nk)$ 的，考虑使用线段树优化建边。

我知道有个人在P2034发了个这样的题解，然而他的线段树建边解法较复杂，最重要的是他带两个 $log$，而我的能优化到一个 $log$。