Problem

2 /3


1-k BFS

Problem

يتم إعطاؤك رسم بياني مرجح موجه. تحتاج إلى العثور على المسافة من أعلى 1 إلى الآخرين ، باستخدام الخوارزمية 1 - k BFS .
& nbsp؛
إدخال
يحتوي السطر الأول & nbsp؛ على عددين صحيحين n و m ، عدد الرؤوس والحواف في الرسم البياني ، على التوالي. تحتوي سطور m التالية على 3 أرقام لكل منها a و b - القمم التي تربط الحافة و c - وزن هذه الحافة (a، b، c & gt؛ = 0).
& nbsp؛
الإخراج
من الضروري إخراج رقم n-1 مفصولة بمسافة - المسافات من أعلى 1 لجميع الآخرين ، إذا لم يكن هناك مسار ممكن من 1 إلى i قمة الرأس ، فأنت بحاجة إلى إخراج مستحيل .
نبسب ؛

نبسب ؛

أمثلة <الجسم>
# إدخال الإخراج
1 <قبل> 9 9 1 2 1 2 4 2 4 6 1 4 3 1 3 5 2 5 6 1 8 9100 9 7100 7 8100 <قبل> 1 4 3 6 4 Impossible Impossible Impossible & nbsp؛
& nbsp؛

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!