====== سوال ۱۸ ======

در گراف ساده‌ی $G$ به هر یال $e$ عدد $w_e$ نسبت داده شده، همچنین هر کدام از یال‌های آن با یکی از دو رنگ سیاه و سفید رنگ شده است که آن را با $c_e$ نشان می‌دهیم. گراف $G$ و به همراه $w$ و $c$ تمام یال‌ها و راس $s$ و راس $t$ به شما داده می‌شوند، شما باید مسیری از $s$ به $t$ پیدا کنید که هزینه‌ی آن بهینه باشد. هزینه‌ی یک مسیر برابر است با مربع مجموع وزن‌های یال‌های سیاه آن مسیر به اضافه تعداد یال‌های سفید آن مسیر. یعنی:

$$l(P)=\Biggl( \sum_{e \in P,c(e)=black} w_e \Biggr)^2 + |\{e \in P |c(e)= white\}|$$

و شما $l(P)$ که می‌یابید بین $s$ و $t$‌ است را کمینه کنید.

===== ورودی =====

برای گراف $G$ ماتریس $A$ به این صورت تعریف می‌شود که در صورتی که عنصر سطر $i$ و ستون $j$ ماتریس $A$، عدد $x$ باشد، اطلاعاتی که از این عدد به‌دست می‌آید به این صورت است:

  * صفر بودن $x$ به معنای عدم وجود یال بین راس $i$ ام و راس $j$ ام است.
  * $|x|$ نشان‌دهنده‌ی وزن یال بین راس $i$ ام و راس $j$ ام است.
  * مثبت بودن $x$ به معنی سیاه بودن یال مورد نظر است.
  * منفی بودن $x$ به معنی سفید بودن یال مورد نظر است.

در فایل ورودی نخست $n$ تعداد راس‌های گراف و سپس شماره‌ی راس‌های $s$ و $t$ به همین ترتیب آمده. سپس در $n$ سطر بعدی نیمه‌ی پایین ماتریس $A$ آمده.($2\leq n \leq200$ و $1\leq w_v\leq 200$)

===== خروجی =====

در فایل خروجی نخست $l(P)$ را بنویسید. و در سطر بعد نخست تعداد راس‌های مسیر $P$ سپس به ترتیب شماره‌ی راس‌هایی که در مسیر از $s$ به $t$ آمده‌اند را بنویسید. راس $t$ و $s$ را نیز بنویسید.



===== ورودي و خروجي نمونه =====

<WRAP :en>
^  ورودي نمونه  ^  خروجي نمونه  ^
|5 1 3 \\ 1 \\ 0 1 \\ 0 0 -1 \\ -1 0 0 1|3 \\ 4 1 5 4 3|

</WRAP>



  * [[سوال ۱۹|سوال بعد]]
  * [[سوال ۱۷|سوال قبل]]