DAG 的最長與最短路徑 (AP325 P-7-6)

輸入一個 DAG（有向無環圖）以及 \(s\) 與 \(t\) 兩點，計算 \(s\) 到 \(t\) 的最短與最長簡單路徑的長度。兩點之間可能有多個邊。

輸入格式

第一行是兩個正整數 \(n\) 與 \(m\)，代表點數與邊數，點以 \(0 \sim n-1\) 編號；第二行兩個整數 \(s\) 與 \(t\)；接下來有 \(m\) 行，每行三個整數 \(u\)、\(v\)、\(w\)，代表一條有向邊 \((u, v)\) 的長度是 \(w\)。

限制

• \(1 \le n \le 10^4\)。
• \(1 \le m \le 10^5\)。
• \(0 \le s, t \le n-1\)，且 \(s \ne t\)。
• \(0 \le u, v \le n-1\)，\(|w| \le 10^4\)（\(w\) 可以是負數）；同一對點之間可能有多條邊。
• 輸入保證是個 DAG。

輸出格式

第一行輸出最短路徑長度，第二行輸出最長路徑長度；如果 \(s\) 到不了 \(t\)，兩行皆輸出 No path。

評分說明

每筆計分測資獨立計分，每筆 5 分，共 100 分；範例不計分。

範例輸入 1

5 6
0 4
0 2 3
0 3 1
2 1 -2
3 4 0
1 4 2
2 4 3

範例輸出 1

1
6

範例輸入 2

4 3
2 0
2 1 5
1 3 0
0 1 1

範例輸出 2

No path
No path

題目來源

本題出自中正大學吳邦一教授所著《AP325－從 APCS 實作題檢測三級到五級》（v1.5）第 7 章 P-7-6，第 243 頁；經作者同意於 AACPOJ 免費公開。教材下載：AP325 講義（Google Drive）；Python 版：AP325-Python（HackMD）。