【NOI2018】归程 排行榜


时间限制: 4 s
空间限制: 512 MB

题目背景

本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。

魔力之都可以抽象成一个 $n$ 个节点、$m$ 条边的无向连通图(节点的编号从 $1$ 至 $n$)。我们依次用 $l,a$ 描述一条边的长度海拔

作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边

我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有积水的。

题目描述

Yazid 是一名来自魔力之都的 OIer,刚参加完 ION2018 的他将踏上归程,回到他温暖的家。

Yazid 的家恰好在魔力之都的 $1$ 号节点。对于接下来 $Q$ 天,每一天 Yazid 都会告诉你他的出发点 $v$ ,以及当天的水位线 $p$。

每一天,Yazid 在出发点都拥有一辆。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。

Yazid 非常讨厌在雨天步行,因此他希望在完成回家这一目标的同时,最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。

本题的部分测试点将强制在线,具体细节请见【输入格式】和【子任务】。

输入格式

从标准输入读入数据。

单个测试点中包含多组数据。输入的第一行为一个非负整数 $T$,表示数据的组数。接下来依次描述每组数据,对于每组数据:

对于输入中的每一行,如果该行包含多个数,则用单个空格将它们隔开。

输出格式

输出到标准输出。

依次输出各组数据的答案。对于每组数据:

样例一

输入

输出

解释

第一天没有降水,Yazid 可以坐车直接回到家中。

第二天、第三天、第四天的积水情况相同,均为连接 $1,2$ 号节点的边、连接 $3,4$ 号点的边有积水。

对于第二天,Yazid 从 $2$ 号点出发坐车只能去往 $3$ 号节点,对回家没有帮助。因此 Yazid 只能纯靠徒步回家。

对于第三天,从 $4$ 号节点出发的唯一一条边是有积水的,车也就变得无用了。Yazid 只能纯靠徒步回家。

对于第四天,Yazid 可以坐车先到达 $2$ 号节点,再步行回家。

第五天所有的边都积水了,因此 Yazid 只能纯靠徒步回家。

样例二

输入

输出

解释

本组数据强制在线。

第一天的答案是 $0$,因此第二天的 $v=\left( 5+0-1\right)\bmod 5+1=5$,$p=\left(2+0\right)\bmod\left(3+1\right)=2$。

第二天的答案是 $2$,因此第三天的 $v=\left( 2+2-1\right)\bmod 5+1=4$,$p=\left(0+2\right)\bmod\left(3+1\right)=2$。

第三天的答案是 $3$,因此第四天的 $v=\left( 4+3-1\right)\bmod 5+1=2$,$p=\left(0+3\right)\bmod\left(3+1\right)=3$。

子任务

所有测试点均保证 $T\leq 3$,所有测试点中的所有数据均满足如下限制:

为了方便你快速理解,我们在表格中使用了一些简单易懂的表述。在此,我们对这些内容作形式化的说明:

$n$$m$$Q=$测试点图形态海拔强制在线
$\leq 1$$\leq 0$$0$1不保证一种
$\leq 6$$\leq 10$$10$2
$\leq 50$$\leq 150$$100$3
$\leq 100$$\leq 300$$200$4
$\leq 1500$$\leq 4000$$2000$5
$\leq 200000$$\leq 400000$$100000$6
$\leq 1500$$=n-1$$2000$7一条链不保证
8
9
$\leq 200000$$100000$10一棵树
11
$\leq 400000$12不保证
13
14
$\leq 1500$$\leq 4000$$2000$15
16
$\leq 200000$$\leq 400000$$100000$17
18
$400000$19
20

为了优化你的阅读体验,我们在表格中把测试点的编号放在了中间,请注意这一点。

题目来源

NOI 2018 Day 1


关于标准输出的说明(最后更新:2018年10月23日)

标准输出将被重定向到内存中,所以你的内存使用量也包括了你的标准输出的大小(向上取整到 4KB 的倍数)。

如果你的程序要进行大量输出,请考虑这一点。




Judge Duck Online | 评测鸭在线
Server Time: 2019-06-27 01:57:08 | Loaded in 0 ms | Server Status
个人娱乐项目,仅供学习交流使用