#Algo2008. 归程

    ID: 296 远端评测题 4000ms 512MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>数据结构并查集图论最短路luogu2018NOI

归程

题目描述

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

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

作为季风气候的代表城市,魔力之都时常有雨水相伴,因此道路积水总是不可避免的。由于整个城市的排水系统连通,因此有积水的边一定是海拔相对最低的一些边。我们用水位线来描述降雨的程度,它的意义是:所有海拔不超过水位线的边都是有积水的。

Yazid 是一名来自魔力之都的 OIer,刚参加完 ION2018 的他将踏上归程,回到他温暖的家。Yazid 的家恰好在魔力之都的 11 号节点。对于接下来 QQ 天,每一天 Yazid 都会告诉你他的出发点 vv ,以及当天的水位线 pp

每一天,Yazid 在出发点都拥有一辆车。这辆车由于一些故障不能经过有积水的边。Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。 需要特殊说明的是,第二天车会被重置,这意味着:

  • 车会在新的出发点被准备好。
  • Yazid 不能利用之前在某处停放的车。

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

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

输入格式

单个测试点中包含多组数据。输入的第一行为一个非负整数 TT,表示数据的组数。

接下来依次描述每组数据,对于每组数据:

第一行 22 个非负整数 n,mn,m,分别表示节点数、边数。

接下来 mm 行,每行 44 个正整数 u,v,l,au, v, l, a,描述一条连接节点 u,vu, v 的、长度为 ll、海拔为 aa 的边。 在这里,我们保证 1u,vn1 \leq u,v \leq n

接下来一行 33 个非负数 Q,K,SQ, K, S ,其中 QQ 表示总天数,K0,1K \in {0,1} 是一个会在下面被用到的系数,SS 表示的是可能的最高水位线。

接下来 QQ 行依次描述每天的状况。每行 22 个整数 v0,p0v_0, p_0 描述一天:

  • 这一天的出发节点为 $v = (v_0 + K \times \mathrm{lastans} - 1) \bmod n + 1$。
  • 这一天的水位线为 $p = (p_0 + K \times \mathrm{lastans}) \bmod (S + 1)$。

其中 lastans\mathrm{lastans} 表示上一天的答案(最小步行总路程)。特别地,我们规定第 11 天时 lastans=0\mathrm{lastans} = 0。 在这里,我们保证 1v0n1 \leq v_0 \leq n0p0S0 \leq p_0 \leq S

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

输出格式

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

  • 输出 QQ 行每行一个整数,依次表示每天的最小步行总路程。
1
4 3
1 2 50 1
2 3 100 2
3 4 50 1
5 0 2
3 0
2 1
4 1
3 1
3 2
0
50
200
50
150
1
5 5
1 2 1 2
2 3 1 2
4 3 1 2
5 3 1 2
1 5 2 1
4 1 3
5 1
5 2
2 0
4 0
0
2
3
1

提示

更多样例

更多样例请在附加文件中下载。

样例 3

见附加文件中的 return3.inreturn3.ans

该样例满足海拔为一种,且不强制在线。

样例 4

见附加文件中的 return4.inreturn4.ans

该样例满足图形态为一条链,且强制在线。

样例 5

见附加文件中的 return5.inreturn5.ans

该样例满足不强制在线。

样例 1 解释

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

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

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

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

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

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

样例 2 解释

本组数据强制在线。

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

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

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

数据范围与约定

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

  • n2×105n\leq 2\times 10^5m4×105m\leq 4\times 10^5Q4×105Q\leq 4\times 10^5K{0,1}K\in\left\{0,1\right\}1S1091\leq S\leq 10^9
  • 对于所有边:l104l\leq 10^4a109a\leq 10^9
  • 任意两点之间都直接或间接通过边相连。

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

  • 图形态:对于表格中该项为 “一棵树” 或 “一条链” 的测试点,保证 m=n1m = n-1。除此之外,这两类测试点分别满足如下限制:
    • 一棵树:保证输入的图是一棵树,即保证边不会构成回路。
    • 一条链:保证所有边满足 u+1=vu + 1 = v
  • 海拔:对于表格中该项为 “一种” 的测试点,保证对于所有边有 a=1a = 1
  • 强制在线:对于表格中该项为 “是” 的测试点,保证 K=1K = 1;如果该项为 “否”,则有 K=0K = 0
  • 对于所有测试点,如果上述对应项为 “不保证”,则对该项内容不作任何保证。
nn mm Q=Q= 测试点 形态 海拔 强制在线
1\leq 1 0\leq 0 00 1 不保证 一种
6\leq 6 10\leq 10 1010 2
50\leq 50 150\leq 150 100100 3
100\leq 100 300\leq 300 200200 4
1500\leq 1500 4000\leq 4000 20002000 5
200000\leq 200000 400000\leq 400000 100000100000 6
1500\leq 1500 =n1=n-1 20002000 7 一条链 不保证
8
9
200000\leq 200000 100000100000 10 一棵树
11
400000\leq 400000 12 不保证
13
14
1500\leq 1500 4000\leq 4000 20002000 15
16
200000\leq 200000 400000\leq 400000 100000100000 17
18
400000400000 19
20