正解=最小生成树
显然拆完路后,这是一棵树,
题目要求访问所有点,
不难发现,除根节点外,每一个点的访问次数=该点的度
每给当前生成树一条边,则该边连接的两点都会增加一个度
因此一条边的实际权值 = 边长+该边所连两点的点权
然后用Kruskal做最小生成树即可
根结点的反问次数会多一,所以直接找个点权最小的点做根节点即可
注册一个 Vijos 通用账户,您就可以在我们提供的所有在线评测服务上提交代码、参与讨论。
使用您的 Vijos 通用账户