10039: Railroads ★★☆☆☆ 題組：Problem Set Archive with Online Judge 解題者：林珈均 解題日期：2019年3月28日 題意： 輸入：C個城市的名稱(string, 1 < C <= 100)以及T輛火車(T <= 1000)，接下來會有T組火車的描述，描述包含這輛火車會停留ti個站，以及這ti個站的抵達時間與站名。最後是出發的時間、出發的城市與目的地的城市名稱。 輸出：最晚離開與最快抵達目的地的時間，若無法抵達則輸出No connection
題意範例： //輸入： 2 //兩筆測資 3 Hamburg Frankfurt Darmstadt //三座城市與他們的名字 3 //三輛火車 2 0949 Hamburg 1006 Frankfurt //停兩站 抵達時間&城市 2 1325 Hamburg 1550 Darmstadt 2 1205 Frankfurt 1411 Darmstadt 0800 Hamburg Darmstadt //出發時間&出發地&目的地 //測資1輸出： Scenario 1 Departure 0949 Hamburg Arrival 1411 Darmstadt
//繼續輸入： 2 Paris Tokyo 1 2 0100 Paris 2300 Tokyo 0800 Paris Tokyo //測資2輸出： Scenario 2 No connection
解法： 首先根據題目所給的資訊建構出一個有向圖(digraph)。 由出發點到目的地嘗試所有搭乘的可能性(BFS)。 同時為了避免城市數量與火車數量很大的狀況造成TLE，將每次嘗試的結果記錄下來避免重複執行(DP)。 最後有解的話輸出最快抵達且最晚出發的結果，無解則輸出No connection。
三個城市： Hamburg Frankfurt Darmstadt 三輛火車 2 0949 Hamburg 1006 Frankfurt 解法範例： 以第一組測資為例： 三個城市： Hamburg Frankfurt Darmstadt 三輛火車 2 0949 Hamburg 1006 Frankfurt 2 1325 Hamburg 1550 Darmstadt 2 1205 Frankfurt 1411 Darmstadt 0800 Hamburg Darmstadt 0949 1006 1205 1411 Hamburg Frankfurt Darmstadt 1325 1550
解法範例： H→F F→D 0949 1006 1205 1411 H→D 1325 1550 ★solution1: H→F→D 0949 1411 solution2: H→D 1325 1550 0949 1006 1205 1411 Hamburg Frankfurt Darmstadt 1325 1550
解法範例： 四個城市：D C A B 三輛火車 3 0800 A 1400 D 1500 C 2 0700 A 0800 B 3 0810 B 0850 C 1423 D 0600 A D 1423 0850 D C 1400 1500 0850 0810 0800 B A 0800 0700
解法範例： A→B B→C C→D D→C 0700 0800 0810 0850 0850 1423 1400 1500 A→D 0700 0800 0810 0850 0850 1423 1400 1500 A→D 0800 1400 solution1: A→B→C→D 0700 1423 ★solution2: A→D 0800 1400 1423 0850 D C 1400 1500 0850 0810 0800 B A 0800 0700
討論： (1) 使用新建的struct來儲存有向圖中的一條線，包含起終點與時間 (2) 使用vector來儲存所有的線 (3) 宣告一個 int[T][C](初始都為No connection，可用-1表示) 來儲存已經嘗試過的路線(在T時間抵達編號C的城市的最晚出發時間)，減少運算時間