本题的故事发生在魔力之都,在这里我们将为你介绍一些必要的设定。
魔力之都可以抽象成一个个节点、条边的无向连通图(节点的编号从至)。我们依次用描述一条边的长度、海拔。
作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边。
我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有积水的。
Yazid 是一名来自魔力之都的 OIer,刚参加完 ION2018 的他将踏上归程,回到他温暖的家。
Yazid 的家恰好在魔力之都的号节点。对于接下来天,每一天 Yazid 都会告诉你他的出发点,以及当天的水位线。
每一天,Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。
Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。
Yazid 非常讨厌在雨天步行,因此他希望在完成回家这一目标的同时,最小化他步行经过的边的总长度。请你帮助 Yazid 进行计算。
本题的部分测试点将强制在线,具体细节请见「输入格式」和「子任务」。
单个测试点中包含多组数据。
输入的第一行为一个非负整数 T,表示数据的组数。
接下来依次描述每组数据,对于每组数据:
• 第一行 2 个非负整数 n, m,分别表示节点数、边数。
• 接下来 m 行,每行 4 个正整数 u, v, l, a,描述一条连接节点 u, v 的、长度为 l、海
拔为 a 的边。
– 在这里,我们保证 1 ≤ u, v ≤ n。
• 接下来一行 3 个非负数 Q, K, S,其中 Q 表示总天数,K ∈ {0, 1} 是一个会在下面
被用到的系数,S 表示的是可能的最高水位线。
• 接下来 Q 行依次描述每天的状况。每行 2 个整数 v0, p0 描述一天:
– 这一天的出发节点为 v = (v0 + K × lastans − 1) mod n + 1。
– 这一天的水位线为 p = (p0 + K × lastans) mod (S + 1)。
– 其中 lastans 表示上一天的答案(最小步行总路程)。特别地,我们规定第 1
天时 lastans = 0。
– 在这里,我们保证 1 ≤ v0 ≤ n,0 ≤ p0 ≤ S。
对于输入中的每一行,如果该行包含多个数,则用单个空格将它们隔开
依次输出各组数据的答案。对于每组数据:
输出 Q 行每行一个整数,依次表示每天的最小步行总路程。
第一天没有降水,Yazid 可以坐车直接回到家中。
第二天、第三天、第四天的积水情况相同,均为连接 1, 2 号节点的边、连接 3, 4 号
点的边有积水。
对于第二天,Yazid 从 2 号点出发坐车只能去往 3 号节点,对回家没有帮助。因此
Yazid 只能纯靠徒步回家。
对于第三天,从 4 号节点出发的唯一一条边是有积水的,车也就变得无用了。Yazid
只能纯靠徒步回家。
对于第四天,Yazid 可以坐车先到达 2 号节点,再步行回家。
第五天所有的边都积水了,因此 Yazid 只能纯靠徒步回家。
本组数据强制在线。
第一天的答案是 0,因此第二天的 v = (5 + 0 − 1) mod 5 + 1 = 5,p = (2 + 0) mod
(3 + 1) = 2。
第二天的答案是 2,因此第三天的 v = (2 + 2 − 1) mod 5 + 1 = 4,p = (0 + 2) mod
(3 + 1) = 2。
第三天的答案是 3,因此第四天的 v = (4 + 3 − 1) mod 5 + 1 = 2,p = (0 + 3) mod
(3 + 1) = 3。
所有测试点均保证 T ≤ 3,所有测试点中的所有数据均满足如下限制:• n ≤ 2 × 105,m ≤ 4 × 105,Q ≤ 4 × 105,K ∈ {0, 1},1 ≤ S ≤ 109。• 对于所有边:l ≤ 104,a ≤ 109。• 任意两点之间都直接或间接通过边相连。为了方便你快速理解, 我们在表格中使用了一些简单易懂的表述 在. 此,我们对这些内容作形式化的说明:.• 图形态:对于表格中该项为“一棵树”或“一条链”的测试点,保证 m = n − 1。除此之外,这两类测试点分别满足如下限制:– 一棵树:保证输入的图是一棵树,即保证边不会构成回路。– 一条链:保证所有边满足 u + 1 = v。• 海拔:对于表格中该项为“一种”的测试点,保证对于所有边有 a = 1。• 强制在线:对于表格中该项为“是”的测试点,保证 K = 1;如果该项为“否”,则有 K = 0。• 对于所有测试点,如果上述对应项为“不保证”,则对该项内容不作任何保证。