春运中的烦恼

《春运中的烦恼》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、春运中的烦恼时限：1秒　内存：64M背景：OIBen身在郑州，京广、陇海两大铁路就交汇在这个城市。每当春运，郑州就成了归家人群的集散地。春运高峰，郑州铁路局加开了不少车次，以满足旅客们的需求，但这样一来，原有的车次安排乱了许多。铁路局局长在中学时代痴迷OI，对二进制数情有独钟，采取了以下措施“疏导交通”（姑且加上引号吧^_^）：每个城市的车站都各自有一个独一无二的编号（十进制）和一个状态（二进制）。车站的状态是交替变换的，对于某一车站，持续“状态0”的时间和持续“状态1”的时间是一定的。如果在某一段时间，A、B两车站的状态相同，则旅客

2、必然可以从A乘一列火车到B（因为车次很多，旅客可以在这段时间的任意时刻找到一辆到B的火车，乘客上车后，火车立即出发），也必然可以从B乘一列火车到A。如果两车站状态不同，旅客就只能等待，因为只有两站状态相同的时段，才有火车可乘。OIBen想尽快回家，这就要靠您的智慧来帮忙了^_^。输入：　　本提有多组数据，每组数据之间有一个空行。　　对于每组输入数据：第1行：车站数2≤N≤300和铁路数1≤M≤20000。第2行：两个数，分别是OIBen所在地火车站的编号和其老家所在地火车站的编号。其下N行：每行四个数（以空格隔开），描述一个车站。这四

3、个数分别是：状态K（“0”或“1”)、这种状态的剩余持续时间T（1≤T≤100）、车站持续“状态0”的时间Tzero（1≤Tzero≤100）、车站持续“状态1”的时间Tone（1≤Tone≤100）。若K为0，保证１≤T≤Tzero；若K为1，保证1≤T≤Tone。其下M行：每行三个数，描述一条铁路。前两个数表示铁路的两端所在的火车站编号，最后一个数表示这条铁路连接的两站之间的单程耗时X（1≤X≤100）。以上输入数据均为整数。对于每个测试数据，保证有唯一解。输出：对于每一组数据，如果OIBen能够乘火车回家，您的程序应产生两行输出

4、：第一行：OIBen回家的最短耗时（从整个系统开始运做到OIBen到达目的地之间的时间）。第二行：一系列数，表示OIBen途经的车站的编号，中间用空格隔开，行末请不要留多余空格。如果OIBen不能乘火车回家，输出应产生一行输出，内容为“PoorOIBen.”（引号不属于输出范围）。样例输入：3113135780152102121531251029101147571001311643011306904106407849914925741357801521021215314966814171731929234826627592816298

5、721094358371838573986453846784764497541055562157285830591761012788279397102189718109391067样例输出：PoorOIBen.501071提示：　　样例数据不利于调试，利于调试的数据请自行设计^_^