در گراف ساده‌ی $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$ را نیز بنویسید.

• سوال بعد
• سوال قبل