Module: bfs。上級コース


Problem

2 /3


1-k BFS

Problem

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

 

例
<頭> <本体>
 

time 1000 ms
memory 32 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# 入力 出力
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 不可能 不可能 不可能