同学们，我们今天来学习基础 dijkstra。
给一个序列，求总和前 \(k\) 小的子序列，分别输出它们的和。\(k,n\le 10^6\)。
dijkstra 主要是用来解决一些“前 \(k\) 小/大”的问题的。具体地，我们将状态视为点，状态带权，则需要连一些满足偏序关系的边，使得“状态”是可以用小复杂度的信息表示的，“状态”到“状态”是可以在小复杂度内转移的，并且边数量级也应是可接受的。最理想的情况下应构成一棵外向树。
对，好像本质其实是优化建图。
那么来考虑这一个问题，我们发现对于一个状态，可以选定最左侧的可右移的点右移若干个（不超过下一个点），得到一个更劣的状态。所有状态都是可达的（你可以逆变换回去。）。所以我们现在每个状态有 \(\Theta(n)\) 条转移边，状态本身也要记录不少东西，不可接受。
不妨将转移边细化，或者说对不同的转移边做差分。我们可以钦定当前点只往右挪一步，代价是多记录当前点的位置。但是我们发现不用记录状态整个集合的信息了，只要知道上一个点和下一个点在哪里即可。
所以我们可以用三个数表示一个状态：\((x,y,z)\) 表示，上一个点在 \(x\) 待挪动，当前点在 \(y\)，下一个点在 \(z\)。则可以转移到 \((x,y+1,z)\) 和 \((x-1,x+1,y)\)。再多记录一个和就全对了。
这就是 dijkstra 算法的最基础应用，你可以使用它通过 P6646，快去试试吧。