HBC20970[NOI2018]归程题解

想要检验自己的编程水平？来试试全网最全C++题库，让您在挑战中不断进步。

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定， 魔力之都可以抽象成一个个节点、条边的无向连通图（节点的编号从至），我们依次用描述一条边的长度、海拔， 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的，由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边， 我们用水位线来描述降雨的程度。

本题的故事发生在魔力之都，在这里我们将为你介绍一些必要的设定。 魔力之都可以抽象成一个个节点、条边的无向连通图（节点的编号从至）。我们依次用描述一条边的长度、海拔。 作为季风气候的代表城市，魔力之都时常有雨水相伴，因此道路积水总是不可避免的。由于整个城市的排水系统连通，因此有积水的边一定是海拔相对最低的一些边。 我们用水位线来描述降雨的程度，它的意义是：所有海拔不超过水位线的边都是有积水的。 Yazid 是一名来自魔力之都的 OIer，刚参加完 ION2018 的他将踏上归程，回到他温暖的家。 Yazid 的家恰好在魔力之都的号节点。对于接下来天，每一天 Yazid 都会告诉你他的出发点，以及当天的水位线。 每一天，Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。 Yazid 可以在任意节点下车，这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是，第二天车会被重置，这意味着： 车会在新的出发点被准备好。 Yazid 不能利用之前在某处停放的车。 Yazid 非常讨厌在雨天步行，因此他希望在完成回家这一目标的同时，最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。 本题的部分测试点将强制在线，具体细节请见「输入格式」和「子任务」。

标签： HBC20970[NOI2018]归程题解