Open Johnny850807 opened 6 years ago
訓練目的：演算法、資料結構、圖論
你要送貨，從某地送到某地，地圖上有許多座標跟許多條路， 每條路皆連接著兩個地點，且每條路皆被賦予一個權重，權重越大代表這條路越不好走或越長， 你必須選擇一條最短最輕鬆的路徑 (權重總合為最小)。
程式第一行會輸入總共有n個地點， 從第二行開始則會依序先接受n個地點之地名及座標的資料，以地名 作為格式， 然而在接收完n個地點的資料之後，接著是所有路段的資料， 以地名1 地名2 路段權重作為格式(代表此路段連接著地名1以及地名2)。 最後一行則會以ASK:開頭 並給予兩個地名，該兩地則為你的起始點以及出發點。
地名
地名1 地名2 路段權重
ASK:
程式最後印出最短路徑，以格式地名1 -> 地名 2 -> 地名3 -> ... -> 地名k輸出
地名1 -> 地名 2 -> 地名3 -> ... -> 地名k
範例輸入：
13 台北 基隆 新莊 桃園 大溪 復興 新豐 關西 瑞芳 平溪 雙溪 頭城 宜蘭 台北 桃園 7 台北 新莊 2 桃園 新莊 3 桃園 新豐 4 新莊 新豐 4 新莊 大溪 1 大溪 關西 3 新豐 關西 5 大溪 復興 2 復興 宜蘭 2 台北 基隆 3 基隆 瑞芳 2 瑞芳 平溪 4 瑞芳 雙溪 4 平溪 雙溪 6 平溪 頭城 4 雙溪 頭城 4 頭城 宜蘭 5 ASK: 台北 宜蘭
範例輸出：
台北 → 新莊 → 大溪 → 復興 → 宜蘭 7
訓練目的：演算法、資料結構、圖論
你要送貨，從某地送到某地，地圖上有許多座標跟許多條路， 每條路皆連接著兩個地點，且每條路皆被賦予一個權重，權重越大代表這條路越不好走或越長， 你必須選擇一條最短最輕鬆的路徑 (權重總合為最小)。
程式第一行會輸入總共有n個地點， 從第二行開始則會依序先接受n個地點之地名及座標的資料，以
地名作為格式， 然而在接收完n個地點的資料之後，接著是所有路段的資料， 以地名1 地名2 路段權重作為格式(代表此路段連接著地名1以及地名2)。 最後一行則會以ASK:開頭 並給予兩個地名，該兩地則為你的起始點以及出發點。程式最後印出最短路徑，以格式
地名1 -> 地名 2 -> 地名3 -> ... -> 地名k輸出範例輸入：
13 台北 基隆 新莊 桃園 大溪 復興 新豐 關西 瑞芳 平溪 雙溪 頭城 宜蘭 台北 桃園 7 台北 新莊 2 桃園 新莊 3 桃園 新豐 4 新莊 新豐 4 新莊 大溪 1 大溪 關西 3 新豐 關西 5 大溪 復興 2 復興 宜蘭 2 台北 基隆 3 基隆 瑞芳 2 瑞芳 平溪 4 瑞芳 雙溪 4 平溪 雙溪 6 平溪 頭城 4 雙溪 頭城 4 頭城 宜蘭 5 ASK: 台北 宜蘭
範例輸出：
台北 → 新莊 → 大溪 → 復興 → 宜蘭 7