هزارتوی دانش
Problem
جاذبه "لابیرنت دانش" در مدرسه تابستانی کامپیوتر (LCS) ساخته شد. هزارتو از N اتاق تشکیل شده است که از 1 تا N شماره گذاری شده اند که برخی از آنها دارای درهایی بین خود هستند. هنگامی که شخصی از دری عبور می کند، شاخص دانش او به میزان معینی که برای این در تعیین شده تغییر می کند. ورودی هزارتو در اتاق 1، خروجی – در اتاق N. هر دانش آموز دقیقاً یک بار از پیچ و خم می گذرد و بسته به میزان دانش به دست آمده در یک یا آن گروه مطالعه قرار می گیرد (هنگام ورود به ماز، این شاخص صفر است). وظیفه شما نشان دادن بهترین نتیجه است.
ورودی:
خط اول ورودی شامل اعداد صحیح N (1 <= N <= 2000) – تعداد اتاق و M (1 <= M <= 10000) – تعداد درب. هر یک از خطوط M بعدی شامل توضیحات درب – تعداد اتاق هایی که از آنها منتهی می شود و به آنها منتهی می شود (شما فقط می توانید در یک جهت از در عبور کنید) و همچنین یک عدد صحیح که هنگام عبور از در به مقدار دانش اضافه می شود (این عدد نمی تواند بیش از 10000 در مدول). درها می توانند از یک اتاق به خود منتهی شوند، می تواند بیش از یک در بین دو اتاق وجود داشته باشد.
خروجی:
نمایش ":)" – اگر می توانید مقدار نامحدودی از دانش را به دست آورید، ":(" – اگر نمی توان از هزارتو عبور کرد، و در غیر این صورت حداکثر مقدار دانش به دست آمده است.
نمونه‌ها
<سر>
| # |
ورودی |
خروجی |
<بدن>
| 1 |
2 2
1 2 3
1 2 7
|
7 |