解题思路

思路

每个点只有一条出边，因此从任意起点出发的路径完全确定。小规模时可以直接模拟；若每个点的入度也为一，图由若干个有向环组成，可以按环批量处理；一般情形则用二进制倍增同时维护跳转点、边权和与边权最小值。

做法

子任务 1：逐步模拟

对于每个起点，重复 $k$ 次：累计当前点的出边权值、更新最小值，再移动到出边终点。总时间复杂度为 $O(nk)$，适用于 $n,k\le 200$。

子任务 2：置换函数图

当每个点的入度均为一时，每个连通分量都是一个有向环。按出边顺序列出环上的点，并建立双倍环的边权前缀和。

设环长为 $L$。将 $k$ 写成 $qL+r$：完整走过的 $q$ 圈贡献 $q$ 倍环权值总和，剩余 $r$ 条边由双倍环前缀和得到。若 $q>0$，最小值必为全环最小边权；否则可对双倍环上长度固定为 $r$ 的窗口使用单调队列，一次求出所有起点的最小值。每个点只进入常数次处理，总时间复杂度为 $O(n)$。

子任务 3：二进制倍增

对每个非负整数 $j$ 和点 $i$，维护三项信息：从 $i$ 出发走 $2^j$ 条边后的终点、这段路径的边权和、这段路径的最小边权。

第零层就是每个点的一条出边。把两段长度均为 $2^{j-1}$ 的路径首尾相接即可得到第 $j$ 层：终点继续跳转一次，边权和相加，最小值取两段最小值的较小者。

回答某个起点时，将 $k$ 按二进制拆分。依次处理所有为一的二进制位，把相应倍增长度的路径接到当前路径之后，同时更新总和、最小值和当前点。

正确性证明

对倍增层数归纳。第零层准确描述一条出边。若第 $j-1$ 层正确，则从点 $i$ 走 $2^j$ 条边恰好由两段连续的 $2^{j-1}$ 条边组成；转移式分别正确合并终点、和与最小值，所以第 $j$ 层也正确。

查询时，$k$ 的二进制展开把所需路径无重无漏地划分为若干个倍增长度的连续段。算法按路径顺序拼接这些段，并对所有段的边权和做加法、对所有段的最小值取最小，因此最终得到的正是恰好 $k$ 条边的总和与最小值。

复杂度

预处理层数为 $O(\log k)$。满分算法的时间复杂度为 $O(n\log k)$，空间复杂度为 $O(n\log k)$。

数值范围

边权总和最大为 $10^{10}\times 10^8=10^{18}$，需要使用 64 位有符号整数。边权最小值可用 32 位整数保存。