內容
隨著捷運線的增加，台北市捷運局決定開發一個 App，來提供大眾更便利的捷運搭乘經驗。這個 App需要在任何時間點，找出給定之兩個捷運站之間，不含等車時間的最短搭車時間。所有捷運線都在 06:00從第一站與最後一站同時列車進站對開，每隔五分鐘就發一班車，最後一班車則在 23:55發車。捷運到站後（包含起站）停留時間都是一分鐘 (所以第一班車其實是在 06:01離站)。為了確保 App的實用性，使用者抵達某捷運站時間必須早於該站捷運開車時間，才能順利的搭上捷運。舉例而言，若抵達時間為 13:55，而欲搭的捷運於 13:54抵達，且將於 13:55開車，那麼本班車就趕不上，必須等待下一班車。但若是 13:54抵達捷運站，則立刻搭上本班捷運（雖然要一分鐘後捷運才會離站）。
輸入說明
第一行有兩個正整數 n, m (1 <= n <= 10, 1 <= m <= 100 )，以空白隔開，代表共有 n條捷運線，且有 m個交叉點，每個交叉點代表兩條捷運線共站，本題不會有三條或三條以上的捷運線共站。接下來的 n行，每行都有四個以上的正整數 i, k, s1, s2,..., sk，連續兩個數字之間以空白隔開，其中 i (1 <= i <= 100 )為捷運線代號， k (2 <= k <= 20 )為該捷運線總站數，sp (1≤p≤k) 代表從(p-1)號站到 p號站所需的行車時間(以分鐘為單位)，因為 s1是起站，因此 s1一定是 0。接下來有 m行，每行四個正整數 i, p, j, q，連續兩個數字之間以空白隔開，代表 i號捷運線的 p號站與 j號捷運線的 q號站共站。最後有五行的使用者測試資料，每行有六個數字： hh, mm, i, p, j, q，連續兩個數字之間以空白隔開，代表 App使用者可於 hh:mm (6 <= hh <= 23, 0 <= mm <= 59 )前抵達 i號捷運線的 p號站且希望前往 j號捷運線的 q號站。
輸出說明
| 每個使用者測試資料都有一行的輸出，共五行。每行一個正整數，代表抵達目的地捷運站所需搭乘捷運最短時間(以分鐘為單位)，此時間不包含初始等待捷運或轉搭另一捷運線時在月台等待捷運進站時間。所有的測試資料都會在捷運停駛前可以抵達目的地。 |
| 以輸入範例(參閱下一頁)第一個測資： 6 0 10 1 10 3為例，使用者於 06:00抵達 10號捷運線的 1號站，目的地為 10號線的 3號站，因此搭乘捷運所需的最短 |
| 時間為： 1分鐘 (在捷運上等待離站) + 2分鐘 (到達2號站所需時間) + 1分鐘 (在捷運上等待離站) + 2分鐘 (到達 3號站所需時間) = 6分鐘。若以輸入範例第四個測資：12 7 2 1 10 1 為例，使用者於 12:07抵達 2號捷運線的 1號站，目的地為 10號線的 1號站，因此搭乘捷運所需的最短時間為：1分鐘 (12:10之捷運進站後搭上捷運並在捷運上等待離站) + 4分鐘 (到達 2號站所需時間) + 1分鐘 (2號線於 12:15到站後下車等待 12:18抵達的 10號線，上車並在捷運上等待離站) + 2分鐘 (到達10號線2號站所需時間) + 1分鐘 (在捷運上等待離站) + 2分鐘 (到達 10號線 1號站所需時間) = 11分鐘。 |
範例輸入
#1
3 3 10 7 0 2 2 3 2 1 3 2 3 0 4 4 7 5 0 5 1 1 3 10 3 2 2 7 2 10 5 7 4 2 3 6 0 10 1 10 3 6 12 10 7 10 1 13 55 2 1 2 3 12 7 2 1 10 1 23 0 10 5 2 3
範例輸出
#1
6 19 10 11 4
測資資訊：
記憶體限制：
512
MB
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1K
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
公開 測資點#0 (20%): 2.0s , <1K
公開 測資點#1 (20%): 2.0s , <1K
公開 測資點#2 (20%): 2.0s , <1K
公開 測資點#3 (20%): 2.0s , <1M
公開 測資點#4 (20%): 2.0s , <1M
提示 ：
標籤:
出處:
100學年度全國資訊學科能力競賽
[管理者：
stanley17112
...
(Stanley)
]