1552 . 無盡的長廊
TopCoder
Tags
Description
相信大家都對「角色扮演遊戲」（Role Playing Game，簡稱 RPG）不陌生吧？
在 RPG 遊戲中，玩家扮演某個設定的時空世界背景中所塑造的一個人物或者幾個隊員角色在特定場景下進行遊戲，進而扮演這位人物。
角色根據不同的遊戲情節和統計數據（例如生命值、法力、力量、靈敏度、智力等等）
具有不同的能力，而這些屬性會根據遊戲規則做對應的改變，扮演的人物跟故事之間也會發生各種的互動。
曉涵最近迷上了一款在某電視遊樂器平台上的一款角色扮演遊戲，
內容大致上是描述一段 愛 與 青春 與 淚水 的感人故事。
然而，現在曉涵遭遇到大麻煩了！
在經過了一連串曲折層疊的事件後，現在角色所位於的場景 ── 一座華麗雄偉的宮殿 受不了強大的撞擊而即將倒塌！！
如果沒有在時間限制之內逃出，就會失敗並且結束遊戲（Game Over）⋯⋯
著急的曉涵一時間失去冷靜，雖然手中已握有這座宮殿的地圖，但卻沒辦法冷靜下來好好仔細思考最好的逃生路徑。
知道了這件事情的你，決定幫曉涵的忙，讓她能度過這個危機！
這座宮殿是由 $N$ 個小房間（編號 $1 \sim N$）以及 $M$ 條長廊連接著這些房間或出口，
現在，曉涵的人物位於編號 $1$ 的房間，出口的編號為 $N+1$ ，請你找出一條合理且最快速的逃生路徑，以逃出這座即將倒塌的宮殿。
Input Format
測試資料的第一行有兩個正整數 $N (N \le 1000000), M (M \le 5000000)$，
第二行開始連續 $M$ 行有三個正整數 $Rm1, Rm2, Len$ 表示著各條長廊的資訊，（$1 \le Rm1 \le Rm2 \le N+1, 1 \le Len \le 100000$）
分別代表著該條長廊兩端的房間以及其長度。
※每條長廊都是單向的，方向為 $Rm1 \rightarrow Rm2$，走錯方向會被石塊砸死。
※對於同樣的一組房間，有可能有兩條以上的長廊連接之。
Output Format
請輸出兩行，分別代表最短的逃生時間以及最佳逃生路徑，格式請參考 Sample Output。
（注意：如果有多條逃生路徑都可以達到最短逃生時間的要求，請輸出字典順序最小的那一個。）
※為了簡化問題，我們把 $1$ 單位的路徑長就視為需要 $1$ 單位的時間，且你無須考慮遊戲人物移動的速度，你可以假設是以等速率移動。
Sample Input 1
3 5 2 3 5 1 3 7 1 2 3 2 4 1 3 4 9
Sample Output 1
4 1-2-4
Hints
※如果你成功的幫曉涵逃出這座即將倒塌的宮殿，你將獲得一個 AC 作為獎勵（這絕對不是好人卡）。
※如果可以有逃出的可能但你給出的結論卻沒能幫曉涵逃出，除了曉涵會遭受 Game over 的結果外，你也將得到一個 WA 作為處罰！！
※如果你的計算速度太慢，導致還來不及計算出是否能逃出以及逃生路徑曉涵的人物就被瓦礫堆壓死，你將得到一個 TLE 作為懲罰！！
Scoring:
對於 22% 的測試資料，$N \le 1000, M \le 2000$對於 33% 的測試資料，$N \le 20000, M \le 50000$
2021.04.09 Update:
- Added $\LaTeX$ ＆by FHVirus
- 放寬記憶體限制
Problem Source
原TIOJ1552 / 第二屆快樂暑假營 -- 最終練習比賽
Problem Setter: Skyly
Subtasks
| No. | Testdata Range | Score |
|---|---|---|
| 1 | 0 | 11 |
| 2 | 1 | 11 |
| 3 | 2 | 11 |
| 4 | 3 | 11 |
| 5 | 4 | 11 |
| 6 | 5 | 11 |
| 7 | 6 | 11 |
| 8 | 7 | 23 |