1077 . F.捷運漫遊
TopCoder
Description
在現代化的城市當中，大眾運輸交通工具往往是極為重要的，可以說是貫穿整個城市的命脈。在方便而迅速的交通網絡之下，整個城市就像是有骨有肉的生命體彼此勾聯牽動在一起。不但對民眾來說更加便利舒適，就整個都市而言也更能發揮其完整的機能。所以好的捷運路線設計不但要在適切的地方設置停靠站，行車路線和行車間隔也必須要好好的規畫一番，車廂的舒適度如果能夠提高或者甚至沿途的風景能夠賞心悅目的話，那就更完美了。
大泡伏很幸運的居住在這樣一個捷運系統相當完善的城市當中，在城市的各處都設置了捷運的停靠站，在捷運站之間，會有著固定週期發車的捷運行駛。任何兩個捷運站之間可能沒有捷運行駛，也可能只有單向有車行駛，就算雙向有車，發車的週期和行駛速度也可能不相等。所幸這些資訊都是相當完整且隨處可得的。
在一個風和日麗的假日，大泡伏從家裡附近的捷運站出發，和小雷約好在某個捷運站的出口會合碰面一起去玩，而心情輕快的大泡伏選擇早早就從家中出門。看著時間還早，他突然興起了一個念頭，就是先搭捷運在城市裡亂逛一陣子了不要出站，最後再在約定的時間之前趕到約會地點就好了。畢竟在這樣一個偷得浮生半日閒的日子裡，輕鬆寫意地瀏覽城市百態也是一種享受。然而看著手中的捷運路線圖，大泡伏卻發現由於每個站的發車週期並不一致，所以他如果任意在捷運站之間上下轉乘，可能會花相當多的時間在等車之上，但他真正喜歡的是在捷運舒適的車廂之中觀察窗外的景物，而不是在捷運站裡面乾等。於是他馬上有了一個疑問，要怎樣轉乘搭車才能讓他花越少的時間在等車上，並且能讓他在約定的時間之前到達他和小雷約會的車站呢？注意到等車和等人是同樣的難耐，所以他也不希望太早到目的車站下車然後枯等直到約定的時間，最後這段等人的時間也應該要一併考慮進去才是。
Input Format
輸入包含了多筆測試資料。每一筆測試資料的第一行有兩個正整數 $N\ M (1 ≤ N ≤ 100)$，這代表所有可以轉乘的捷運站數目，我們將這些捷運站從 $1$ 到 $N$ 編號。接下來有 $M$ 行，每行包含四個以空白分隔的正整數 $A_i\ B_i\ P_i\ T_i $ $(1 ≤ A_i, B_i ≤ N, 1 ≤ T_i ≤ 100, 1 ≤ P_i≤ 100, 1 ≤ i ≤ M)$，代表從捷運站 $A_i$ 到 $B_i$ 之間每隔 $P_i$ 分鐘便會發一班車，行駛需要花去 $T_i$ 分鐘的時間。每兩個不同的捷運站之間頂多只會有一條同向的班車，也不會有起站和終站為同一站的班車。接下來的一行有兩個以空白字元分隔的正整數 $N_b\ N_e(1 ≤ N_b, N_e≤ N)$，代表大泡伏出發的車站和欲到達的車站編號。最後兩行有兩個代表時間的字串，格式是 $\text{HH:MM} (00 ≤ \text{HH} ≤ 23, 00 ≤ \text{MM} ≤ 59)$，分別代表大泡伏從捷運站出發啟程的時間以及和小雷約定時間。所有路線在每天 $0$ 時 $0$ 分的時候都會發一班車，然後接下來每隔前面所述的週期就再發一班車，直到該天結束為止。大泡伏出發的時間和他們約定會合的時間一定在同一天之內。另外，你可以假設大泡伏可以在一瞬間內下車並轉搭另一班捷運列車。
當讀到 $N = M = 0$ 時，代表測試檔案結束。請不要對這一行輸入作任何輸出。
Output Format
對於每一筆輸入檔案中的測試資料，應該在一行中輸出一個整數，代表大泡伏從指定的捷運站出發的時間開始，一直到約定的會合時間為止，可能的最少等待時間 (包括等車以及等人)。如果不存在任何一種搭車方式使得泡伏來得及在約定時間之內到達目的地，請對這筆輸入輸出一行「No way」。
Sample Input 1
1 2 4 3
1 3 3 3
3 4 7 1
3 5 5 2
4 6 5 3
5 6 7 4
2 6 3 2
1 6
07:00
07:12
0 0
Sample Output 1
Hints
Problem Source
原TIOJ1077 / NPSC2005決賽(prob F)
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 100 |