Find The Shortest Path 4
あなたは
n 個の都市と、それらの都市を結ぶ m 本の双方向道路からなる地図を与えられています。各道路には という非負の整数による長さが割り当てられています。あなたのタスクは、都市 1 から都市 n への最短経路を見つけることです。💡
この課題では、最短経路の長さだけでなく、その経路自体も求める必要があることに注意してください。
Input
最初の行には、都市の数
n と道路の数 m () がスペース区切りで与えられます。続く
m 行には、それぞれ 3 つの整数 、、 がスペース区切りで与えられます。これは、都市 と都市 を結ぶ長さ の道路を示しています（）。Output
1 行目には、スペース区切りで 2 つの整数
k と l を出力してください。ここで k は最短経路に含まれる都市の数、l は最短経路の長さを表します。次の行には、
k 個の都市を最短経路の順にスペース区切りで出力します。もし複数の最短経路が存在するなら、そのうちのどれを出力しても構いません。また、ここでは
k を最小化する必要はありません。Examples
入力 (Input) | 出力 (Output) |
4 5
1 2 3
1 3 5
2 4 3
3 4 3
1 4 7 | 3 6
1 2 4 |
Constraints
Time limit: 4 seconds
Memory limit: 512 MB
Output limit: 5 MB