归程

提交数: 51, 通过率: 52.94%, 平均分: 58.92

题目描述:

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

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

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

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

 

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

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

每一天,Yazid 在出发点都拥有一辆。这辆车由于一些故障不能经过有积水的边。

Yazid 可以在任意节点下车,这样接下来他就可以步行经过有积水的边。但车会被留在他下车的节点并不会再被使用。

  • 需要特殊说明的是,第二天车会被重置,这意味着:
    • 车会在新的出发点被准备好。
    • Yazid 不能利用之前在某处停放的车。

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

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

 

输入格式:

从文件 return.in 读入数据。

单个测试点中包含多组数据。输入的第一行为一个非负整数 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)modn+1。
    • 这一天的水位线为 p=(p0+K×lastans)mod(S+1)。
    • 其中 lastans 表示上一天的答案(最小步行总路程)。特别地,我们规定第 1 天时 lastans=0。
    • 在这里,我们保证 1≤v0≤n,0≤p0≤S。

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

输出格式:

输出到文件 return.out 中。

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

  • 输出 Q 行每行一个整数,依次表示每天的最小步行总路程。

样例输入:

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

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

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

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

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

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

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

 

N<=200000,M<=400000,0<=K<=1,Q<=400000,T<=3

1<=S<=1e9,l<=10000,a<=1e9

2901-3.png

时间限制: 6000ms
空间限制: 512MB

来源: NOI2018