#P18951. [Mladen Manev 2022 AT1] commute / 乘公交回家

[Mladen Manev 2022 AT1] commute / 乘公交回家

乘公交回家

有 NN 个城市和 MM 条无向道路,每条道路连接两个不同城市,给出正整数通行时间。任意两城至多有一条直接道路。有 SS 条公交线路。

一条线路用三个整数 L,x,yL,x,y 和 LL 个互不相同的城市 c1,…,cLc_1,\ldots,c_L 描述。相邻城市之间保证有道路。车辆在时刻 x+jyx+j y(整数 j≥0j\ge0)从 c1c_1 出发,依次经过所列城市,通行时间等于相应道路的时间。可以在任意途经城市上下车,上下车耗时忽略。该线路只沿给出的顺序运行。

你在时刻 TT 位于城市 11,只能乘公交和等待,不可步行沿道路移动。最多换乘 KK 次,即最多乘坐 K+1K+1 辆车。求最早到达城市 NN 的时刻;不能到达则输出 NIE。

输入格式

第一行 N,M,S,K,TN,M,S,K,T。接下来 MM 行,每行为 u,v,wu,v,w,表示道路及其通行时间。

随后依次描述 SS 条线路:一行 L,x,yL,x,y,下一行 LL 个城市编号。

输出格式

一个整数,表示最早到达时刻;或者字符串 NIE。所有时间使用同一单位,计算过程及答案可能超出 32 位整数。

数据范围

2≤N≤100002\le N\le10000,1≤M≤500001\le M\le50000,1≤S≤250001\le S\le25000,0≤K≤1000\le K\le100,0≤T≤1090\le T\le10^9。

2≤L≤N2\le L\le N,所有线路的 LL 之和不超过 5000050000;0≤x≤1090\le x\le10^9,1≤y,w≤1091\le y,w\le10^9。

样例

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 分。