d100. P_7_6 DAG的最長與最短路徑

Content

DAG(directed acyclic graph)是指一種沒有環路的有向圖，DAG 是應用很多的一個圖的類別，我們在很多前置關係的問題上都有類似的情形。

例如一件計畫分成很多工作，某些工作必須在某些工作完成之後才能進行。我們可以將每個工作看成一個點，若 u 是 v 的前置工作，就在圖上加入一個(u,v)有向邊，這樣建立出來的圖必須是個DAG，否則就會產生雞生蛋蛋生雞的矛盾而有某些工作無法完成。

輸入一個DAG以及 $s$ 與 $t$ 兩點，計算 $s$ 到 $t$ 的最短與最長簡單路徑的長度。兩點之間可能有多個邊。

Input

第一行是兩個正整數 $n$ 與 $m$ ，代表點數與邊數，點以 $0 \sim (n-1)$ 編號，第二行兩個整數 $s$ 與 $t$ ，

接下來有 $m$ 行，每行三個整數 $u, v, w$ 代表一條有向邊 $(u,v)$ 的長度是 $w$ 。

$n$ 不超過 $10^4$ ，$m$ 不超過 $10^5$， $w$ 的絕對值不超過 $10^4$ 。輸入保證是個 DAG 。

Output

第一行輸出最短路徑長度，第二行輸出最長路徑長度，如果不存在，兩者皆輸出”No path”。

Sample Input #1

Sample Output #1

1
6

Sample Input #2

Sample Output #2

No path
No path

測資資訊：

記憶體限制： 256 MB
公開測資點#0 (10%): 1.0s , <1K
公開測資點#1 (10%): 1.0s , <1M
公開測資點#2 (10%): 1.0s , <1M
公開測資點#3 (10%): 1.0s , <1M
公開測資點#4 (10%): 1.0s , <10M
公開測資點#5 (10%): 1.0s , <10M
公開測資點#6 (10%): 1.0s , <10M
公開測資點#7 (10%): 1.0s , <10M
公開測資點#8 (10%): 1.0s , <10M
公開測資點#9 (10%): 1.0s , <10M

Hint ：

Tags:

ch7

出處:

Prof. Wu [管理者：

ktlai (K．我已霸榜．Tlai)

]

ID	User	Problem	Subject	Hit	Post Date
沒有發現任何「解題報告」