#P9402. [POI 2020/2021 R3] Droga do domu
[POI 2020/2021 R3] Droga do domu
题目背景
译自 XXVIII Olimpiada Informatyczna - III etap Droga do domu。
d1t1。
题目描述
个点, 条边,无重边自环,边有长度。
号点是学校, 号点是家。
条公交线路。公交逢点必停,且一个点不会停两次。在一条边上行驶的时间就是它的长度。给定了第一班公交发车时间和发车间隔。
在时刻 从学校出发,至多换乘 次,求最早什么时候到家。
只计算路上时间和等车时间。换乘时间不计。
输入格式
第一行:五个整数 。
接下来 行:每行三个整数 ,表示有一条边连接 ,长度为 。
接下来 行:每两行描述一条公交线路:
- 第一行三个整数 ,表示它共停靠 个点,第一班在时刻 发车,每两班之间时间间隔为 。
- 第二行 个整数 ,依次为它停靠的 个点。
输出格式
一行一个整数,答案。
如果不能到家,那么输出一行一个字符串 NIE
。
提示
样例解释:
对于全部数据,,,,,,,,,,,。
子任务编号 | 限制 | 分数 |
---|---|---|
1 | 20 | |
2 | ||
3 | ||
4 | ||
5 |