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

Content

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

Input

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

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

n 不超過 1e4 ，m 不超過 1e5， w 的絕對值不超過 1e4 。輸入保證是個 DAG 。

Output

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

Sample Input #1

Sample Output #1

1
6

Sample Input #2

Sample Output #2

No path
No path

測資資訊：

記憶體限制： 512 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 [管理者： s710426(?0_o)//) ]

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