Negcycle. چرخه منفی
Problem
یک نمودار جهت دار وزنی داده شده است. لازم است مشخص شود که آیا دارای چرخه وزن منفی است یا خیر. تضمین می شود که تمام رئوس نمودار از اولین راس قابل دسترسی باشد.
ورودی:
خط اول فایل ورودی شامل دو عدد طبیعی n و m — تعداد رئوس و یال های نمودار به ترتیب ( n ≤ 1 111، m ≤ 11 111).
خطوط m بعدی شامل توضیحات لبه ها، یکی در هر خط است. لبه i با سه عدد bi، ei و wi — اعداد انتهای دنده و وزن آن به ترتیب (1 ≤ bi، ei ≤ n، &منهای 100 000 ≤ Wi ≤ 10) . توجه داشته باشید که نمودار می تواند چندین لبه و حلقه داشته باشد.
خروجی:
خط اول فایل خروجی باید حاوی بله باشد اگر نمودار دارای چرخه وزن منفی و خیر — در غیر این صورت.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
4 4
2 1-4
1 2 1
3 4 2
2 3 3
| بله |
| 2 |
4 6
2 1 4
1 2 1
3 4 2
2 3 3
1 1 2
1 2 2
| نه |