You are not allowed to perform this action

Game

شما در صورتی از این سوال نمره کسب می‌کنید که به همه تست ها پاسخ درست بدهید.

سعید و رضا هر کدام یک گراف همبند وزن‌دار $n$ رأسی دارند و تصمیم گرفته اند که با استفاده از آن ها بازی زیر را انجام دهند: 

 
*  در ابتدا مقدار $x_0$ برابر با $s$ است.
*  سعید و رضا به نوبت مراحل بازی را انجام می‌دهند و سعید شروع کننده بازی است.
*  در مرحله $i$ ام بازی کن عدد $x_i$ را برابر با یکی از همسایه‌های رأس $x_{i-1}$ در گراف خود قرار می‌دهد که فاصله آن از $t$ کمتر از فاصله رأس $x_{i-1}$ از $t$ باشد ، هزینه این مرحله برابر است با وزن یال بین رئوس$x_{i-1}$ و $x_i$ در گراف بازیکن. در صورتی که $x_i$ برابر با $t$ باشد بازی پایان می‌یابد.

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

ورودی

در سطر اول ورودی عدد $1 \leq n \leq 1000$ و $1 \leq s \leq n$ و $1 \leq t \leq n$ آمده است.

در ادامه شرح گراف سعید و رضا به ترتیب به صورت زیر آمده است:

در اولین سطر عدد $n-1 \leq m \leq 10^5$ نشان‌دهنده تعداد یال‌ها و در $m$ سطر بعد در هر سطر سه عدد $ 1 \leq a_i \leq n$ و $ 1 \leq b_i \leq n$ و $1 \leq c_i \leq 10^6$ آمده‌است که نشان می‌دهد یک یال دوطرفه بین رئوس $a_i$ و $b_i$ با وزن $c_i$ وجود دارد.

خروجی

در تنها سطر خروجی پاسخ سوال را چاپ نمایید، اگر این مقدار بی نهایت است، در خروجی $-1$ چاپ کنید.

محدودیت‌ها

  • محدودیت زمان: ۴ ثانیه
  • محدودیت حافظه: ۲۵۶ مگابایت

ورودی و خروجی نمونه

ورودی نمونه خروجی نمونه
5 1 5
5
1 2 2
1 4 2
2 3 1
3 4 1
5 3 1
4
1 2 2
2 4 2
2 3 1
2 5 2		-1
3 1 3
4
1 2 10
2 3 10
1 3 20
2 3 30
4
2 1 10
1 3 10
1 1 10
2 3 10		20

پاسخ

برای حل این مسئله وضعیت‌های بازی را با یک گراف مدل می‌کنیم. وضعیت‌های این بازی را با زوج مرتب (رأسی فعلی، بازیکن فعلی) می‌توان مشخص کرد و چون تعداد این وضعیت‌ها $2n$ می‌باشد، گراف وضعیت‌ها یک گراف 2n$ $ رأسی هست.

یال‌های این گراف معادل حرکات مجاز در بازی می‌باشند. بنابراین اگر $a$ و $c$ را اسم بازیکنان و $b$ و $d$ را اسم دو رأس در نظر بگیریم، از رأس $(c, d)$ به رأس $(a, b)$ می‌توان رفت اگر و فقط اگر هر دوشرط زیر برقرار باشد:

  1. $a$ با $c$ متفاوت باشد. یعنی در یک حرکت باید بازیکن فعلی عوض شود.
  2. در گراف بازیکن $a$ ،فاصله رأس $d$ تا رأس مقصد ($t$) کم‌تر از فاصله‌ی رأس $b$ تا رأس مقصد باشد.

حال مسئله معادل این می‌شود که در گراف وضعیت‌ها گشتی پیدا کنیم که از رأس $(saeed, s)$ شروع شود و جمع یال‌های آن بیشینه شود.( $s$ رأسی بود که بازی از آن شروع می‌شد)

اگر در گراف وضعیت‌ها، دوری وجود داشته باشد که از رأس مبدا قابل دسترسی باشد، در این صورت جواب مسئله بی‌نهایت می‌شود (هر دو بازیکن بازی را همواره در آن دور ادامه می‌دهند). و اگر چنین دوری وجود نداشته باشد، جواب مسئله برابر طولانی‌ترین مسیری است که از رأس مبدا شروع می‌شود. برای اینکه بفهمیم که آیا دور قابل دسترسی از رأس مبدا وجود دارد می‌توانیم از DFS استفاده کنیم. چنین دوری وجود دارد اگر و فقط اگر در اجرای DFS از رأس مبدا حداقل یک یال برگشتی مشاهده کنیم.

اگر یال برگشتی مشاهده کردیم که جواب مسئله بی‌نهایت می‌شود. در غیر این صورت وضعیت‌های قابل دسرسی از رأس مبدأ یک گراف بدون دور را تشکیل می‌دهند و می‌توان طولانی‌ترین مسیر در آن را با استفاده از روش پویا محاسبه کرد.

پیچیدگی

گراف وضعیت‌ها $2n$ تا رأس و حداکثر به اندازه‌ی جمع یال‌های گراف سعید و رضا یال دارد و چون اجرای DFS از $O(v + e)$ زمان می‌برد، کل الگوریتم از $O(n + m)$ اجرا می‌شود.

▸ سوال قبل سوال بعد ◂