回分類題庫
e004: 4.捷運路線
關鍵字: 100學年度全國決賽

測資點 : 6 | Time Limit : 10000 ms | Memory Limit : 128000 KB
Accepted : 18 Times / 16 Users | Submit : 69 Times / 21 Users | Accepted rate : 76%
題目加入時間 : 2015-11-12 09:40

Content: 简体中文

隨著捷運線的增加,台北市捷運局決定開發一個 App,來提供大眾更便利的捷運搭乘經驗。這個 App 需要在任何時間點,找出給定之兩個捷運站之間,不含等車時間的最短搭車時間。所有捷運線都在 06:00 從第一站與最後一站同時列車進站對開,每隔五分鐘就發一班車,最後一班車則在 23:55 發車。捷運到站後(包含起站)停留時間都是一分鐘 (所以第一班車其實是在 06:01 離站)。 為了確保 App 的實用性,使用者抵達某捷運站時間必須早於該站捷運開車時間,才能順利的搭上捷運。舉例而言,若抵達時間為 13:55,而欲搭的捷運於 13:54 抵達,且將於 13:55 開車,那麼本班車就趕不上,必須等待下一班車。但若是 13:54抵達捷運站,則立刻搭上本班捷運(雖然要一分鐘後捷運才會離站)。

Input:

第一行有兩個正整數 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 號站。

Output:

每個使用者測試資料都有一行的輸出,共五行。每行一個正整數,代表抵達目的地捷運站所需搭乘捷運最短時間(以分鐘為單位),此時間不包含初始等待捷運或轉搭另一捷運線時在月台等待捷運進站時間。所有的測試資料都會在捷運停駛前可以抵達目的地。

以輸入範例第一個測資: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 分鐘。 

 

Sample Input:help

若題目沒有特別說明,則應該以多測資的方式讀取,若不知如何讀取請參考 a001 的範例程式。
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 

Sample Output :

6
19
10
11
4 

Hint :

Author :

100學年度全國決賽 (管理員:sagit)

  Solve it!   Status Forum