Problem
負のエッジを持つ有向加重グラフ (負のサイクルなし) が与えられた場合
開始頂点と終了頂点を指定して、それらの間の最小距離を定義します。
入力:
与えられた 4 つの数値 n、m、s、f - それぞれ頂点の数、エッジの数、開始頂点と終了頂点 (1 から開始)。
次の m 行には、頂点 1、頂点 2、および頂点間の遷移の価格の 3 つの数値がそれぞれ含まれています。
出力:
1 つの数字 (タスクの答え) を表示する必要があります。答えがない場合は、Inf を出力します。
例
<頭>
# |
入力 |
出力 |
<本体>
1 |
4 2 1 4
1 2 100500
2 3 100500
|
Inf |
表>