P4768

[NOI2018] 归程

题目描述

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

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

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

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

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

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

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

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

输入格式

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

接下来依次描述每组数据，对于每组数据：

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

接下来 $m$ 行，每行 $4$ 个正整数 $u, v, l, a$ ，描述一条连接节点 $u, v$ 的、长度为 $l$ 、海拔为 $a$ 的边。在这里，我们保证 $1 \leq u,v \leq n$ 。

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

接下来 $Q$ 行依次描述每天的状况。每行 $2$ 个整数 $v_0, p_0$ 描述一天：

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

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

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

输出格式

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

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

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

样例 1 解释

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

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

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

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

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

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

样例 2 解释

本组数据强制在线。

第一天的答案是 $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\leq 2\times 10^5$ ， $m\leq 4\times 10^5$ ， $Q\leq 4\times 10^5$ ， $K\in\left\{0,1\right\}$ ， $1\leq S\leq 10^9$ 。
对于所有边： $l\leq 10^4$ ， $a\leq 10^9$ 。
任意两点之间都直接或间接通过边相连。

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

图形态：对于表格中该项为“一棵树”或“一条链”的测试点，保证 $m = n-1$ $m = n - 1$ 。除此之外，这两类测试点分别满足如下限制：
- 一棵树：保证输入的图是一棵树，即保证边不会构成回路。
- 一条链：保证所有边满足 $u + 1 = v$ 。
海拔：对于表格中该项为“一种”的测试点，保证对于所有边有 $a = 1$ 。
强制在线：对于表格中该项为“是”的测试点，保证 $K = 1$ ；如果该项为“否”，则有 $K = 0$ 。
对于所有测试点，如果上述对应项为“不保证”，则对该项内容不作任何保证。

$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			是
$\leq 1500$	$\leq 4000$	$2000$	16
$\leq 200000$	$\leq 400000$	$100000$	17
		$100000$	18
		$400000$	19
		$400000$	20

题解

1 篇题解

登录后即可使用 Markdown 发布题解。

YuyiLv.6👑 站长管理员

P4768 [NOI2018] 归程题解 Author: Yuyi 题意分析题目的要求很清晰：Yazid 要从节点 $v$ 回到节点 $1$。前半段他可以坐车，条件是经过的边的海拔必须严格大于水位线 $p$；一旦他下了车，剩下的路就只能步行，而且要求步行距离最短。也就是说，在给定的水位线 $p$ 下，Yazid 坐车可以在“海拔 $ p$ 的子图”里随…

点击展开完整题解点击收起题解

2026年8月9日 18:52

P4768 [NOI2018] 归程题解

Author: Yuyi

题意分析

题目的要求很清晰：Yazid 要从节点 $v$ 回到节点 $1$ 。前半段他可以坐车，条件是经过的边的海拔必须严格大于水位线 $p$ ；一旦他下了车，剩下的路就只能步行，而且要求步行距离最短。也就是说，在给定的水位线 $p$ 下，Yazid 坐车可以在“海拔 $> p$ 的子图”里随意跑。他坐车能到达的任何点，都可以作为他步行的起点。为了最小化步行距离，他自然应该在所有能坐车到达的点中，挑选一个距离终点（节点 $1$ ）最短的点下车。

正解推导过程

Dijkstra 预处理最短路：因为是无向图，且终点固定为 $1$ 。我们直接以 $1$ 为源点跑一遍 Dijkstra，求出所有点到点 $1$ 的最短距离 $d[i]$ 。
Kruskal 重构树建树：因为我们要找的是“海拔 $> p$ $> p$ 的子图”，这涉及到边的连通性。我们将所有边按海拔从大到小降序排序，然后跑 Kruskal 建重构树。
- 这样建出来的树，越往根节点海拔越低，越往叶子节点海拔越高。
- 任何一个叶子节点（原图的节点）在水位线 $p$ 下能坐车到达的所有点，恰好就是他在重构树上某个祖先的整个子树！
维护子树最值：在建重构树的同时，让每一个虚拟节点维护一下它子树里所有叶子节点的 $d[i]$ 的最小值 min_d。
倍增查询处理：面对 $Q$ 次在线查询，我们拿着起点 $v$ ，利用树上倍增（LCA里的 f 数组）不断向上跳，只要祖先节点的海拔严格 $> p$ 我们就跳上去。跳到最高点后，这个点记录的 min_d 就是该连通块里距离点 $1$ 的最短步行距离，直接 $O(1)$ 拿下答案！

正解代码及分析

#include <bits/stdc++.h>
#define ll long long
#define inf 0x3f3f3f3f
#define eps 1e-9
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define dep(i,a,b) for(int i=(a);i>=(b);i--)
#define lowbit(a) (a)&(-a)
using namespace std;
const int maxn = 400005; // 重构树最多 2N-1 个点，约 40万
const int maxm = 800005; // 无向图双向建边，M最大40万，开 80万
const int mo = 998244353;
const double pi = acos(-1.0);
template <typename T>
inline void read(T &X)
{
    X = 0;int w = 0; char ch = 0;
    while(!isdigit(ch)) {w |= ch == '-' ;ch = getchar();}
    while(isdigit(ch)) X = X * 10 + (ch^48),ch = getchar();
    if(w) X = -X;
}
int n,m;
int head[maxn],edge_cnt;
int to[maxm],nxt[maxm],w[maxm];
void add(int u,int v,int weight)
{
    edge_cnt++;
    to[edge_cnt] = v;
    w[edge_cnt] = weight;
    nxt[edge_cnt] = head[u];
    head[u] = edge_cnt;
}
struct Edge
{
    int u,v,l,a;
}e[maxn];
bool cmp(Edge A,Edge B)
{
    return A.a > B.a; // 海拔降序排序
}
ll d[maxn];
int vis[maxn];
int fa[maxn];
int find(int u)
{
    if(u == fa[u]) return u;
    return fa[u] = find(fa[u]);
}
int val[maxn],ch[maxn][2],dep_node[maxn],f[maxn][20];
ll min_d[maxn];
void dfs(int u,int father)
{
    dep_node[u] = dep_node[father] + 1;
    f[u][0] = father;
    rep(i,1,19) f[u][i] = f[f[u][i-1]][i-1];
    if(ch[u][0]) dfs(ch[u][0],u);
    if(ch[u][1]) dfs(ch[u][1],u);
}
void solve()
{
    read(n),read(m);
    rep(i,1,n) head[i] = 0; // 多组数据清空邻接表头
    edge_cnt = 0;
    rep(i,1,m)
    {
        read(e[i].u),read(e[i].v),read(e[i].l),read(e[i].a);
        add(e[i].u,e[i].v,e[i].l);
        add(e[i].v,e[i].u,e[i].l);
    }
    // Dijkstra 预处理每个点到点1的最短距离
    rep(i,1,n) d[i] = 1e18,vis[i] = 0;
    priority_queue<pair<ll,int>, vector<pair<ll,int>>, greater<pair<ll,int>>> pq;
    d[1] = 0;
    pq.push({0,1});
    while(!pq.empty())
    {
        int u = pq.top().second;
        pq.pop();
        if(vis[u]) continue;
        vis[u] = 1;
        for(int i = head[u]; i; i = nxt[i])
        {
            int v = to[i];
            if(d[v] > d[u] + w[i])
            {
                d[v] = d[u] + w[i];
                pq.push({d[v],v});
            }
        }
    }
    
    sort(e+1,e+1+m,cmp);
    rep(i,1,n*2) fa[i] = i,ch[i][0] = ch[i][1] = 0;
    rep(i,1,n) min_d[i] = d[i],val[i] = 0;
    int tot = n;
    rep(i,1,m)
    {
        int fu = find(e[i].u);
        int fv = find(e[i].v);
        if(fu != fv)
        {
            tot++;
            fa[fu] = tot;
            fa[fv] = tot;
            ch[tot][0] = fu;
            ch[tot][1] = fv;
            val[tot] = e[i].a;
            min_d[tot] = min(min_d[fu],min_d[fv]); // 虚拟节点记录子树内最短步行距离
        }
    }
    rep(i,1,tot)
    {
        if(fa[i] == i) dfs(i,0); // 重构树 DFS 预处理倍增
    }
    
    int Q,K,S;
    read(Q),read(K),read(S);
    ll lastans = 0;
    while(Q--)
    {
        int v0,p0;
        read(v0),read(p0);
        int v = (v0 + K * lastans - 1) % n + 1;
        int p = (p0 + K * lastans) % (S + 1);
        dep(i,19,0)
        {
            if(f[v][i] && val[f[v][i]] > p) // 只要祖先海拔比水位高，就开车往上跳
            {
                v = f[v][i];
            }
        }
        lastans = min_d[v]; // 跳到最高点后，该连通块里的最短路即为答案
        cout << lastans << '\n'; // Q高达40万次，强制特殊情况处理使用\n替换endl防止TLE
    }
    return;
}
int main()
{
    int T=1;
//  freopen("mul.in","r",stdin);
//  freopen("mul.out","w",stdout);
    read(T); // 本题多组测试数据，必须读入 T
    while(T--) solve();
    return 0;
}

复杂度分析

时间复杂度：
- Dijkstra 跑全图最短路，时间为 $O(M \log M)$ 。
- Kruskal 按海拔排序并建重构树，时间为 $O(M \log M)$ 。
- DFS 预处理倍增数组耗时 $O(N \log N)$ 。
- $Q$ 次在线询问，每次在树上倍增向上跳 $O(\log N)$ ，耗时 $O(Q \log N)$ 。
- 综上，整体单组数据时间复杂度为 $O((M+Q) \log N)$ ，这套组合拳完美应对 $40$ 万级的数据，极其丝滑。
空间复杂度：对于最大 $N=2\times 10^5, M=4\times 10^5$ 的数据，重构树最大扩展到 $2N-1$ 个节点。依照习惯，所有点相关的数组统一定义在 maxn = 400005，双向边相关的存图定在 maxm = 800005。其中消耗最大的是倍增数组 f 大约占 32MB，总内存控制在 80MB 上下，在 NOI 规定的 512MB 内存限额下稳如磐石，空间复杂度 $O(N \log N + M)$ 。

讨论

0 条讨论

登录后即可使用 Markdown 发起讨论和回复。

还没有讨论，来发起第一条吧。

[NOI2018] 归程

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

更多样例

样例 3

样例 4

样例 5

样例 1 解释

样例 2 解释

数据范围与约定

题解

P4768 [NOI2018] 归程题解

题意分析

正解推导过程

正解代码及分析

复杂度分析

讨论

[NOI2018] 归程

题目描述

输入格式

输出格式

输入输出样例

输入样例 #1

输出样例 #1

输入样例 #2

输出样例 #2

说明/提示

更多样例

样例 3

样例 4

样例 5

样例 1 解释

样例 2 解释

数据范围与约定

题解

P4768 [NOI2018] 归程 题解

题意分析

正解推导过程

正解代码及分析

复杂度分析

讨论

P4768 [NOI2018] 归程题解