Module: Ford-Bellman アルゴリズム


Problem

3 /6


ベルマン

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