题目背景

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

魔力之都可以抽象成一个 n 个节点、m 条边的无向连通图(节点的编号从 1 至 n)。

我们依次用 l, a 描述一条边的长度、海拔。

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

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

题目描述

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

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

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

需要特殊说明的是,第二天车会被重置,这意味着:

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

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

输入和输出

从文件 return.in 中读入数据。

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

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

  1. 第一行 2 个非负整数 n, m,分别表示节点数、边数。
  2. 接下来 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 个整数 v_0, p_0 描述一天:

    • 这一天的出发节点为 $v = (v_0 + K × lastans − 1) \mod n + 1$。
    • 这一天的水位线为 $p = (p_0 + K × lastans) \mod (S + 1)$。
    • 其中 $lastans$ 表示上一天的答案(最小步行总路程)。特别地,我们规定第 1天时 $lastans = 0$。
  • 在这里,我们保证 $1 ≤ v_0 ≤ n$,$0 ≤ p_0 ≤ S$。

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

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

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

样例

输入

输出

数据范围和提示

思路

实际上比赛的时候我是想出了正解的(但是我没打完 + 打萎了)。

首先我们发现前11个点都是送分的,尤其是前6个,最短路跑一遍就好了,体现出这是一道签到题。对于一条链。。。$O(n^2)$打打暴力也是可以的,一棵数也就是倍增一下就好了。

正解也很容易想到,把没有积水开车可以相互抵达的点并查集合并,同时维护一个“联通块”里走路到终点的最短路径。题目要求在线,那就用可持久化并查集。

代码

  1. oyyj603470138
    Aug 20, 2018

    为什么不写Kruskal重构树。。
    有好写,跑的又快

    Reply
    • xgzepto
      Aug 20, 2018

      因为没学。

      Reply
  2. oyyj603470138
    Jul 24, 2018

    %%%zyh%%%

    Reply
  3. crazydavehdy
    Jul 21, 2018

    %%%

    Reply