#P18951. [Mladen Manev 2022 AT1] commute / 乘公交回家
[Mladen Manev 2022 AT1] commute / 乘公交回家
乘公交回家
有 个城市和 条无向道路,每条道路连接两个不同城市,给出正整数通行时间。任意两城至多有一条直接道路。有 条公交线路。
一条线路用三个整数 和 个互不相同的城市 描述。相邻城市之间保证有道路。车辆在时刻 (整数 )从 出发,依次经过所列城市,通行时间等于相应道路的时间。可以在任意途经城市上下车,上下车耗时忽略。该线路只沿给出的顺序运行。
你在时刻 位于城市 ,只能乘公交和等待,不可步行沿道路移动。最多换乘 次,即最多乘坐 辆车。求最早到达城市 的时刻;不能到达则输出 NIE。
输入格式
第一行 。接下来 行,每行为 ,表示道路及其通行时间。
随后依次描述 条线路:一行 ,下一行 个城市编号。
输出格式
一个整数,表示最早到达时刻;或者字符串 NIE。所有时间使用同一单位,计算过程及答案可能超出 32 位整数。
数据范围
,,,,。
,所有线路的 之和不超过 ;,。
样例
4 4 2 1 1
1 2 2
2 3 4
1 3 3
4 3 2
4 0 10
1 2 3 4
3 2 7
1 3 2
8
原题
本题由 2022 年训练赛选用,原题为波兰 XXVIII OI 决赛第一天的 Droga do domu(2021)。目录年份按本网站使用年份 2022 整理。
来源与数据说明
2022 年 Dr. Mladen Manev,AT1,原题名 commute。赛事资料,原文题面见附件 statement.pdf。
原官方测试数据未能获取,本题使用依据原题规格编写的自建测试数据,并非官方原始数据。总分为 100 分。