Problem
有向加重グラフが表示されます。ある頂点から別の頂点への最短経路を見つけます。
入力
最初の行には、N、S、および F (1≤N≤100、1≤S、F≤N) の 3 つの数字が含まれています。グラフの頂点の数、S -初期頂点と F –最後の。次の N 行に、それぞれ N 個の数字を入力します (100 を超えない)。グラフ隣接行列。-1 は頂点間にエッジがないことを意味し、負ではない数値を意味します。指定された重みのエッジの存在。ゼロは行列の主対角に書き込まれます。
出力
最短経路の 1 つ (いずれか) のすべての頂点を順番に表示するか、指定された頂点間に経路がない場合は 1 つの数値 -1 を表示する必要があります。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
3 2 1
0 1 1
4 0 1
2 1 0
|
2 3 1 |