Module: bfs. kursus lanjutan


Problem

2 /3


1-k BFS

Problem

Anda diberi graf berwajaran terarah. Anda perlu mencari jarak dari 1 atas ke semua yang lain, menggunakan algoritma 1 - k BFS.
 
Input
Baris pertama mengandungi 2 integer n dan m, masing-masing bilangan bucu dan tepi dalam graf. Baris m berikut mengandungi 3 nombor setiap satu a dan b - bucu yang disambungkan oleh tepi dan c - berat tepi ini (a, b, c >= 0).
 
Output
Ia perlu untuk mengeluarkan nombor n-1 yang dipisahkan oleh ruang - jarak dari 1 atas ke semua yang lain, jika tiada laluan yang mungkin dari 1 ke i< /code> vertex, maka anda perlu mengeluarkan Mustahil.
 

 

Contoh
 

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!

# Input Output
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 Mustahil Mustahil Mustahil Mustahil