部分分
枚举所有点亮灯的顺序即可(适合 nnn 很小的数据)。
正解
把问题转化为最小生成树:若两点之间的花费高于 mmm,就把它改为 mmm。
具体做法是造一个虚点,让虚点连接所有点、边权均为 mmm。从虚点连向某个点的操作,就等价于「直接花费 mmm 点星光能量点亮这盏灯」。在新图上跑一遍最小生成树(Kruskal 或 Prim),得到的边权和就是答案。
这样就把「可以任意选择起点」的问题统一处理掉了,不需要额外枚举起始点。
使用您的 Hydro 通用账户