#P15485. [2026四川省队集训]登山

[2026四川省队集训]登山

登山

题目描述

“为什么要攀登?因为山就在那里。”

慕士塔格山上有 nn 处点位,点从 11 到 nn 编号,tt 号点位为山顶。有 mm 条连接着两个点位的道路,构成一张连通无向简单图。

记 did_i 为 ii 号点位到山顶所需经过的边数,即 ii 到 tt 的最短路的距离。

现在安东·尤丁采夫(Anton)和维亚切斯拉夫·巴兰尼科夫(BVVD)要进行登山活动。

具体的,Anton 驾驶 Su-30MKI 先勘测到整座山的道路连接情况,并用红色或蓝色标记每一条边,

随后 BVVD 从地面上的某个结点出发,一路向山顶走去。

由于 BVVD 记忆力不好,以至于无法记住任何事情,换句话说,他只能根据自己当前所在结点的编号,总点数、每个相邻点的编号以及对应道路的颜色,做出移动到哪个结点的信息。

现在你需要为 Anton 和 BVVD 制定策略。对每个起点 uu,要求在至多 du+Cd_u+C 次移动内到达山顶。目标是让最坏情况下的额外步数 CC 尽可能小。

实现细节

本题是通信题。提交一份包含 #include "mountain.h" 的 C++ 源文件,实现以下两个函数。

std::vector<int> label(int n, std::vector<std::pair<int, int>> edges, int t);
int travel(int n, int node, std::vector<std::pair<int, int>> directions);
  • label 由 Anton 执行。它收到总点数 nn、按输入顺序给出的道路 mathrmedgesmathrm{edges} 和山顶编号 tt。返回长度为 mm 的数组,第 ii 项是第 ii 条边的颜色,00 表示红色,11 表示蓝色。
  • travel 由 BVVD 执行。它收到总点数 nn、当前结点 node,以及相邻点与对应边颜色组成的数组 directions。返回相邻点的编号。到达 tt 后停止移动。
  • 任意两次函数调用之间都不能用全局变量、静态变量、文件等共享信息。每次调用只能根据当前参数计算。请勿定义 main,也请勿使用标准输入输出。
  • 评测时 Hydro 会自动提供接口和入口程序。使用 C++14 或更新版本,直接提交实现这两个函数的源代码。

数据范围与计分

1lenle100001le nle 10000,1lemle500001le mle 50000。每个测试点包含三张图。评测器检查每张图的所有起点,取整个子任务的最大额外步数 CC。任一图染色格式非法、走向非相邻点,或存在无法到达山顶的起点,该子任务得 00 分。

子任务 图的限制 分值
1 完全图 4
2 任意点到山顶的距离至多为 2 10
3 树 11
4 二分图 13
5 梯形图 12
6 无额外限制 50

前五个子任务在 Cle14Cle 14 时得满分。第六个子任务按下表计分。

最大额外步数 CC 得分
Cle14Cle 14 50
15leCle3015le Cle 30 25
31leCle10431le Cle 10^4 5
C>104C>10^4 0

梯形图由两条等长的链、连接两链对应位置的横档以及山顶 tt 构成。tt 连接两条链同一端的两个端点,且 nn 为奇数。

梯形图示意

本地测试

下载本地评测包。将你的实现保存为 mountain.cpp,与评测包中的文件放在同一目录。

g++ mountain.cpp sample-grader.cpp -O2 -std=c++14 -o mountain
./mountain < sample.in

本地样例的第一行给出四个整数 n,m,s,tn,m,s,t,表示点数、边数、起点和山顶。随后 mm 行每行两个整数 u,vu,v,表示一条无向边。本地评测器会输出路线与步数。不同的合法策略可以产生不同的路线。