فهرست مندرجات
Mr.President
قرار است هیئتی از نمایندگان یک کشور برای انجام مذاکراتی به کشور شما بیاید. این افراد در ابتدا در کشور شماره ۱ قرار دارند و با استفاده از هواپیمای مخصوص خود به کشور شما می‌آیند. متاسفانه بین همه کشورها خط هوایی وجود ندارد، به همین دلیل این هیئت لازم دارد برای رسیدن به کشور شما از تعدادی از خطوط هوایی بین کشورها استفاده کند که در نهایت به کشور شما ختم می‌شود. هم‌چنین هر خط هوایی بین دو کشور مشخص می‌کند که این مسافت باید در چند ساعت طی شود و هر هواپیمایی که از آن خط استفاده می‌کند باید حرکت بین آن دو کشور را طوری انجام دهد که زمان آن برابر با مقدار تعیین شده باشد.
پس از مشخص شدن زمان مذاکرات، آقای رئیس‌جمهور به شما خبر می‌دهد که باید مذاکرات $k$ ساعت به تعویق بیافتد. از آنجایی که شما دوست ندارید برنامه مذاکرات را تغییر دهید، تنها راه برای رسیدن به مقصود رئیس‌جمهور این است که کاری انجام دهید که سفر هیئت حداقل $k$ ساعت بیشتر به طول انجامد. شما نمی‌دانید که این سفر با استفاده از چه مسیری انجام می‌شود ولی مطمئن هستنید که این مسیر مسیری است که طول آن کمینه است. شما می‌توانید با دادن مقدار مشخصی پول به رئیس یک خط هوایی زمان مشخص شده برای سفر بین دو کشور مربوط به آن خط را یک ساعت افزایش دهید. به صورت دقیق‌تر برای این که زمان سفر یک خط هوایی را $a$ واحد افزایش دهید باید $a$ برابر مقدار مشخص شده به رئیس آن خط پول دهید. دقت کنید که پس از دادن پول به رئیس‌های خطوط هوایی و تغییر زمان سفر خطوط، هیئت نمایندگان از زمان جدید خطوط با خبر می‌شوند و سفر خود را طوری مشخص می‌کنند که طول سفر آن‌ها در سیستم جدید کمینه باشد. شما می‌خواهید طوری زمان تعیین شده برای خطوط را افزایش دهید که زمان سفر هیئت به کشور شما حداقل $k$ ساعت (نسبت به زمان قبلی) افزایش پیدا کند. شما باید برنامه‌ای بنویسید که با دریافت اطلاعات مربوط به کشورها و خطوط هوایی بین آن‌ها با خرج کمترین هزینه این کار را انجام دهد.
ورودی
- در سطر اول ورودی سه عدد $n$ ، $m$ و $k$، نشان دهنده تعداد کشورها، تعداد خطوط هوایی و میزان زمانی که مذاکره باید به تعویق بیافتد آمده است. کشورها با اعداد بین $1$ و $n$ مشخص شده اند. هیئت در ابتدا در کشور شماره $1$ قرار دارد و کشور شما کشور شماره $n$ است.
- در هر یک از $m$ سطر بعدی به ترتیب ۴ عدد $u_i$ ،$v_i$ $l_i$ و $c_i$ آمده است. این اعداد نشان می‌دهند که یک خط هوایی یکطرفه از کشور $u_i$ به $v_i$ وجود دارد که زمان تعیین شده برای آن $l_i$ ساعت است. شما برای این که یک $a$ ساعت زمان تعیین شده برای این خط را افزایش دهید باید $a.c_i$ واحد پول به رئیس این خط هوایی دهید.
- می‌توانید فرض کنید که امکان سفر از شهر شماره ۱ به شهر شماره $n$ وجود دارد.
- $2 \le n \leq 50$
- $1 \leq k \leq 50$
- $1 \leq m \leq \frac{n.(n-1)}{2}$
- تمامی اعداد ورودی بین ۱ و ۱۰۰۰۰ هستند
- در حداقل ۴۰ درصد تست ها $k$ برابر با ۱ است.
خروجی
در تنها سطر خروجی کمترین پول لازم برای رسیدن به هدف را چاپ نمایید.\\
محدودیت‌ها
- محدودیت زمان: ۵ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
ورودی و خروجی نمونه
| ورودی نمونه | خروجی نمونه |
|---|---|
| 3 3 3 1 2 1 3 2 3 1 4 1 3 3 5 | 19 |
توضیحات
ابزار صفحه
کلیه‌ی حقوق این سایت متعلق به کمیته‌ی ملی المپیاد کامپیوتر ایران است.
