正式训练题面

规则来源

• 赛项说明页码：12-13
• 训练题主题：丝路驿站传信：最少换站次数与最短耗时路径
• 所属赛道：丝路文化赛道

题目背景

丝路传信任务需要从起点驿站把信息送到终点驿站。路线选择时先看换站次数是否最少，若换站次数相同，再比较总耗时。为了便于调度，还要恢复满足双关键字最优的完整路径。

任务描述

• 读取驿站图并建立无向邻接表。
• 先最小化经过的道路条数，也就是换站次数。
• 在换站次数最少的前提下，再最小化总耗时，并输出完整路径。

输入格式

1. 第一行输入 n m s t，表示驿站数、道路数、起点和终点。
2. 接下来 m 行每行输入 u v days，表示一条无向道路及所需天数。

输出格式

1. 可达时第一行输出 relay_count=最少换站次数。
2. 第二行输出 total_days=对应总天数。
3. 第三行输出 path= 后接 a->b->c 形式路径。
4. 不可达时依次输出 relay_count=-1、total_days=-1、path=IMPOSSIBLE。

数据范围与说明

• 2 <= n <= 200。
• 1 <= m <= 1000。
• 1 <= days <= 50。
• 答案保证按“换站次数最少，再总天数最少”后唯一。

样例输入

5 6 1 5
1 2 2
2 5 3
1 3 1
3 4 1
4 5 1
2 3 1

样例输出

relay_count=2
total_days=5
path=1->2->5

样例解释

• 路径 1->2->5 只经过两条道路，因此换站次数为 2。
• 另一条 1->3->4->5 虽然总天数更短，但换站次数为 3，不满足主关键字最优。
• 因此最终答案是 relay_count=2、total_days=5。

知识点清单

• 邻接表建图。
• 双关键字状态比较 (steps, days)。
• 优先队列维护最优状态。
• 前驱数组恢复完整路径。
• 不可达结果输出。