گراف وزن‌دار و جهت‌دار $G$ به ما داده شده ولی وزن تعدادی از یال های آن مشخص نیست هدف مسئله این است که تعدادی عدد داده شده را طوری به یال‌ها‌ی گراف به عنوان وزن نسبت دهیم که وزن کم‌وزن‌ترین دور گراف کمینه شود.

در سطر اول فایل ورودی تعداد رئوس گراف و بعد از آن یک جدول $n\times n$ داده شده است به طوری که اگر در گراف بین دو راس $i$ و $j$‌یال نباشد $a_{i,j}$ برابر ۰ است. اگر یال بدون وزن باشد برابر $-1$ و در غیر این صورت برابر وزن یال بین دو راس می‌باشد. در سطر آخر هم به تعداد یال‌های بدون وزن عدد آمده است. (وزن‌ها عدد طبیعی و کوچک‌تر از ۳۲۰۰۰ هستند و تعداد راس‌ها از ۱۵۰ بیش‌تر نیست. همچنین تعداد یال‌های بدون برچسب حداکثر ۲۰ می‌باشد)

در سطر اول فایل خروجی وزن کم‌وزن‌ترین دور و در سطر بعد دنباله‌ی راس‌های تشکیل‌دهنده‌ی دور و در سطر آخر هم وزن یال‌ها به ترتیب آمده است. هر عدد را حداکثر به یک یال می‌توان نسبت داد.

• سوال بعد
• سوال قبل