2011-05-01-5-uva-10039-railroads.md

layout	title	date	tags
post	[UVa] 10039 - Railroads	2011-05-01	UVa dynamic programming | 動態規劃

題目網址：10039 - Railroads

題目概述

有個人想要搭火車從城市 A 到城市 B。題目會給定此人出發時間以及火車的時刻表，時刻表上有各班列車在各站的時間。

根據該人的出發時間以及火車時刻表，替他規劃出能最早抵達目的城市 B 得路線。

Technique Detail

• 城市數量 C, 1 < C ≤ 100
• 火車數量 T, 1 ≤ 1,000
• 各班火車停靠站數 t_i, t_i ≤ 100
• 轉乘時間為 0 秒

輸入格式

測試資料開頭會有一個整數 K，表示接下來會有 K 筆測試資料。

每筆測試資料分為三個部分，城市資訊、火車資訊、其他。測試資料由城市資訊開始，首先有一個整數 C，表示城市數量。接下來有 C 行，每一行都有一個字串，表示城市名稱。

接下來為火車資訊，由一個整數 T 開始，表示火車數量。接下來就分為 T 個區塊來描述每列火車。每一列火車的描述由一個整數 t_i 開始，接下來會有 t_i 行，每一行代表著該列火車抵達某城市的時刻 T_C。

最後其他資訊的部份有三行，第一行為此人出發的時間 T_A。第二行為出發城市之名稱 City_A，第三行為目的城市之名稱 City_B。

輸入所給的時間格式皆為 HHMM 的格式。

輸出格式

對於每一筆測試資料，首先輸出該測試資料的編號，編號由 1 開始，格式為 Scenario #。若存在該路徑，接下來有兩行，第一行為從出發城市發車的時刻以及城市名稱，格式為 Departure time city。而第三行為抵達目的地城市的抵達時刻與城市名稱，格式為 Arrival time city。若不存在可行路徑，則只要輸出一行 No connection。

每筆測試資料最後加上一個空行。

輸出所使用的時間格式皆為 HHMM 的格式。

---

解題思路

很久以前看過的題目，當時並沒有解出來，一直以為是簡單的 DFS 搜索，結果 submission 充滿了大量 WA 與 TLE。經過不斷的重新思考才發現這個題目是 DP，DP 的狀態為 DP[city][time]，表示在 time 這個時間點抵達 city 最晚出發的火車。由於搭乘時間要最短，所以我們選擇最晚出發的火車。

DP 轉移方程式：

$$ DP(city_x, time_x) = max(DP(city_j, time_x)), city_j \in line_i, line_i \in all\ lines\ pass\ by\ city_x $$

最後的答案為 DP[B][time] 有解的答案中 time 最小的。

Time Complexity: O( C × T )

Source Code

<script src="https://gist.github.com/KuoE0/1610955.js"></script>

Source on gist.