SGU 103 Traffic Lights 翻译 题解

103. 交通灯
每个测试点:0.5s
内存限制:4096KB

　　在Dingilville市城市交通的安排很不寻常，公路连接着路口，在两个不同的路口之间最多有一条公路连接，没有公路会连接一个路口自身。正反向通过一条道路的时间是相同的，在每一个路口都有一个交通灯，在任意时刻它要么是蓝色的要么是紫色的，这些灯的颜色是定期交换的：蓝色持续一段时间，紫色持续一段时间。当一条公路两边的交通灯颜色相同时才允许汽车离开一个路口去另一个路口。如果一辆车到达一个路口时的瞬间交通灯的颜色改变了，那就需要重新考虑新的颜色。车辆允许在一个路口进行等待。你将得到关于城市的下列信息：

• 每条公路通过所需要的时间(整数)
• 每一个路口两种交通灯的颜色的持续时间(整数)
• 和每个路口的交通灯的初始颜色和持续时间(整数) 

　　你的任务就是寻找一辆车从给定起始路口到给定终止路口所需要的最短时间。如果这样的路径不止一个，你只能输出其中的一个。

输入：
　　第一行包括两个数字：起始路口和终止路口。
　　第二行包含两个数字：n和m。
　　接下来的n行包含n个路口的信息：第(i+2)行给出了第i个路口的信息：Ci, riC, tiB, tiP。C就是第i个路口的交通灯的初始颜色，要么是B(蓝色)或者P(紫色)。
　　最后接下来的m行包含m条公路的信息，每行都有： i, j, lij。路口i到路口j由这条公路连接。

　　 2 ≤ N ≤ 300，N代表路口的个数，公路由1～N的整数来标识。 1 ≤ M ≤ 14000，M代表公路的个数。 1 ≤ lij ≤ 100  从路口i到达路口j所需的时间。

2011年6月5日 21时41分50秒---暂时还没翻译完，剩下的明天继续把。