10039: Railroads ★★☆☆☆ 題組：Problem Set Archive with Online Judge

Presentation on theme: "10039: Railroads ★★☆☆☆ 題組：Problem Set Archive with Online Judge"— Presentation transcript:

1 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 題意範例： //輸入： 2 //兩筆測資 3 Hamburg Frankfurt Darmstadt //三座城市與他們的名字 3 //三輛火車 Hamburg 1006 Frankfurt //停兩站 抵達時間&城市 Hamburg 1550 Darmstadt Frankfurt 1411 Darmstadt 0800 Hamburg Darmstadt //出發時間&出發地&目的地 //測資1輸出： Scenario 1 Departure 0949 Hamburg Arrival 1411 Darmstadt

3 //繼續輸入： 2 Paris Tokyo 1 Paris 2300 Tokyo 0800 Paris Tokyo //測資2輸出： Scenario 2 No connection

4 解法： 首先根據題目所給的資訊建構出一個有向圖(digraph)。 由出發點到目的地嘗試所有搭乘的可能性(BFS)。 同時為了避免城市數量與火車數量很大的狀況造成TLE，將每次嘗試的結果記錄下來避免重複執行(DP)。 最後有解的話輸出最快抵達且最晚出發的結果，無解則輸出No connection。

5 三個城市： Hamburg Frankfurt Darmstadt 三輛火車 2 0949 Hamburg 1006 Frankfurt
解法範例： 以第一組測資為例： 三個城市： Hamburg Frankfurt Darmstadt 三輛火車 Hamburg 1006 Frankfurt Hamburg 1550 Darmstadt Frankfurt 1411 Darmstadt 0800 Hamburg Darmstadt 0949 1006 1205 1411 Hamburg Frankfurt Darmstadt 1325 1550

6 解法範例： H→F F→D H→D ★solution1: H→F→D solution2: H→D 0949 1006 1205 1411 Hamburg Frankfurt Darmstadt 1325 1550

7 解法範例： 四個城市：D C A B 三輛火車 3 0800 A 1400 D 1500 C 2 0700 A 0800 B
B 0850 C 1423 D 0600 A D 1423 0850 D C 1400 1500 0850 0810 0800 B A 0800 0700

8 解法範例： A→B B→C C→D D→C 0700 0800 0810 0850 0850 1423 1400 1500 A→D
A→D solution1: A→B→C→D ★solution2: A→D 1423 0850 D C 1400 1500 0850 0810 0800 B A 0800 0700

9 討論： (1) 使用新建的struct來儲存有向圖中的一條線，包含起終點與時間 (2) 使用vector來儲存所有的線 (3) 宣告一個 int[T][C](初始都為No connection，可用-1表示) 來儲存已經嘗試過的路線(在T時間抵達編號C的城市的最晚出發時間)，減少運算時間