P5866 [SEERC 2018] Space Station

Jones 实现了他的梦想：他加入了国际空间站（ISS）的一次任务。他接受了他的第一个任务：检查空间站上的电子设备的工作状况。 ISS 被分为 $N$ 个模块，模块从 $1$ 到 $N$ 编号。Jones 发现，为了提高效率，空间站的设计使任意两个模块之间仅存在一条简单路径。在一次太阳耀斑活动中，连接两个模块的双向通道很容易受到辐射影响。检查一条通道 $i$ 的状况必须花费 $C_i$ 的时间。Jones 需要找到一条从模块 $1$ 出发，经过每条通道至少一次，再回到模块 $1$ 的最快路径。 除了从模块之间的通道中通过之外，Jones 还可以穿上宇航服，跳出空间站，从外面直接从某一模块移动到任意模块上，但是这种方法只能进行最多 $M$ 次。Jones 假设进行一次需要花费固定的时间 $K$。

无

无