Problem
有向加重グラフが表示されます。アルゴリズム 1 - k BFS を使用して、上部の 1 から他のすべてのものまでの距離を見つける必要があります。
入力
最初の行には、2 つの整数 n と m が含まれており、それぞれグラフの頂点とエッジの数です。次の m 行には、それぞれ a と b - エッジが接続する頂点と c - の 3 つの数字が含まれています。この辺の重み (a, b, c >= 0).
出力
スペースで区切られた n-1 の数値を出力する必要があります - 1 から可能なパスがない場合、上部の 1 から他のすべての距離までの距離。 を i< /code> 頂点に変換すると、Impossible を出力する必要があります。
例
<頭>
| # |
入力 |
出力 |
<本体>
| 1 |
<プレ>
9 9
1 2 1
2 4 2
4 6 1
4 3 1
3 5 2
5 6 1
8 9 100
9 7 100
7 8 100
|
<プレ>
1 4 3 6 4 不可能 不可能 不可能
|