P1613. 洞穴突袭者

ID: 614
远程评测题
时间限制: 1000ms
内存限制: 10MiB
尝试次数: 0
通过次数: 0
难度: （无）
上传者: Hydro
标签:

题目描述

Afkiyia是一座大山，山体中有许多洞穴，这些洞穴通过隧道相连。其中一个洞穴里藏着一名恐怖组织头目。每条隧道连接两个洞穴，可能有多条隧道连接同一对洞穴。

在隧道与洞穴的连接处有一道门。恐怖分子会不时关闭隧道两端的门以“清理”隧道。目前尚不清楚他们如何清理隧道，但我们知道：如果有人（或任何生物）在隧道清理期间被困在其中，就会死亡。隧道清理完成后，门会重新打开，隧道可以再次使用。

现在情报人员已经查明了恐怖组织头目藏身的洞穴，并且掌握了隧道的清理时间表。突袭队员Jing需要进入洞穴抓获头目，你需要帮助他找到一条最短时间到达目标洞穴的路线，注意不能在隧道清理期间被困在其中。

输入格式

输入包含多个测试用例。每个测试用例的第一行包含四个正整数 ( n, m, s, t )，分别表示洞穴数（编号1~n）、隧道数（编号1~m）、Jing的起始洞穴s（初始时间为0）和目标洞穴t。（( 1 \leq s, t \leq n \leq 50 )，( m \leq 500 )）。

接下来的m行描述每条隧道的信息：每行是一个由至少35个整数组成的序列（以空格分隔）。前两个整数是隧道连接的两个洞穴；第三个整数是通过隧道所需的时间（从一端到另一端）；后续是一个递增的正整数序列，交替表示隧道的关闭和开启时间。例如：

• 若某行是 10 14 5 6 7 8 9，表示隧道连接洞穴10和14，通过需要5单位时间。隧道在时间6关闭、7开启，然后在8关闭、9开启。这意味着隧道在时间区间 ([6,7)) 和 ([8,9)) 内清理，9之后永远开启。
• 若某行是 10 9 15 8 18 23，表示隧道连接洞穴10和9，通过需要15单位时间。隧道在8关闭、18开启，23关闭，23之后永远关闭。

输入以一个0表示结束。

输出格式

每个测试用例输出一行，若Jing能到达目标洞穴t，输出最短到达时间；否则输出*。注意：若s = t，即Jing初始时就在目标洞穴，输出0。

输入数据示例 1

2 2 1 2  
1 2 5 4 10 14 20 24 30  
1 2 6 2 10 22 30  
6 9 1 6  
1 2 6 5 10  
1 3 7 8 20 30 40  
2 4 8 5 13 21 30  
3 5 10 16 25 34 45  
2 5 9 22 32 40 50  
3 4 15 2 8 24 34  
4 6 10 32 45 56 65  
5 6 3 2 5 10 15  
2 3 5 2 9 19 25  
2 2 1 2  
1 2 7 6 9 12  
1 2 9 8 12 19  
0  

输出数据示例 1

16  
55  
*  

来源

Asia Kaohsiung 2003