#P15485. [2026四川省队集训]登山
[2026四川省队集训]登山
登山
题目描述
“为什么要攀登?因为山就在那里。”
慕士塔格山上有 处点位,点从 到 编号, 号点位为山顶。有 条连接着两个点位的道路,构成一张连通无向简单图。
记 为 号点位到山顶所需经过的边数,即 到 的最短路的距离。
现在安东·尤丁采夫(Anton)和维亚切斯拉夫·巴兰尼科夫(BVVD)要进行登山活动。
具体的,Anton 驾驶 Su-30MKI 先勘测到整座山的道路连接情况,并用红色或蓝色标记每一条边,
随后 BVVD 从地面上的某个结点出发,一路向山顶走去。
由于 BVVD 记忆力不好,以至于无法记住任何事情,换句话说,他只能根据自己当前所在结点的编号,总点数、每个相邻点的编号以及对应道路的颜色,做出移动到哪个结点的信息。
现在你需要为 Anton 和 BVVD 制定策略。对每个起点 ,要求在至多 次移动内到达山顶。目标是让最坏情况下的额外步数 尽可能小。
实现细节
本题是通信题。提交一份包含 #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 执行。它收到总点数 、按输入顺序给出的道路 和山顶编号 。返回长度为 的数组,第 项是第 条边的颜色, 表示红色, 表示蓝色。travel由 BVVD 执行。它收到总点数 、当前结点node,以及相邻点与对应边颜色组成的数组directions。返回相邻点的编号。到达 后停止移动。- 任意两次函数调用之间都不能用全局变量、静态变量、文件等共享信息。每次调用只能根据当前参数计算。请勿定义
main,也请勿使用标准输入输出。 - 评测时 Hydro 会自动提供接口和入口程序。使用 C++14 或更新版本,直接提交实现这两个函数的源代码。
数据范围与计分
,。每个测试点包含三张图。评测器检查每张图的所有起点,取整个子任务的最大额外步数 。任一图染色格式非法、走向非相邻点,或存在无法到达山顶的起点,该子任务得 分。
| 子任务 | 图的限制 | 分值 |
|---|---|---|
| 1 | 完全图 | 4 |
| 2 | 任意点到山顶的距离至多为 2 | 10 |
| 3 | 树 | 11 |
| 4 | 二分图 | 13 |
| 5 | 梯形图 | 12 |
| 6 | 无额外限制 | 50 |
前五个子任务在 时得满分。第六个子任务按下表计分。
| 最大额外步数 | 得分 |
|---|---|
| 50 | |
| 25 | |
| 5 | |
| 0 |
梯形图由两条等长的链、连接两链对应位置的横档以及山顶 构成。 连接两条链同一端的两个端点,且 为奇数。

本地测试
下载本地评测包。将你的实现保存为 mountain.cpp,与评测包中的文件放在同一目录。
g++ mountain.cpp sample-grader.cpp -O2 -std=c++14 -o mountain
./mountain < sample.in
本地样例的第一行给出四个整数 ,表示点数、边数、起点和山顶。随后 行每行两个整数 ,表示一条无向边。本地评测器会输出路线与步数。不同的合法策略可以产生不同的路线。