گراف ساده، وزن‌دار و بدون جهت $G$ و رئوس $s_1,t_1,s_2,t_2$ داده شده است. پس از خواندن فایل ورودی فایل‌های A.Txt،B.Txt،C.Txt و D.Txt را مطابق دستور زیر تولید کنید!

در سطر اول فایل ورودی $n$، تعداد رئوس و اعداد $s_1,t_1,s_2,t_2$ (به ترتیب و با شروع از $s_1$) نوشته شده و در $n-1$ سطر بعدی نیمه‌ی پایین ماتریس مجاورت $G$ آمده است (همه‌ی وزن‌ها اعداد طبیعی‌اند و صفر نشانه‌ی عدم وجود یال است در ضمن $n\leq 100$).

1. اندازه‌ی کوچک‌ترین زیردرخت فراگیر را به دست آورید که در آن حداقل یکی از رئوس $s_1,t_1,s_2,t_2$ برگ باشد. خروجی این بخش فایل A.Txt است که در سطراول آن اندازه‌ی این درخت را می‌نویسید و $n-1$ سطر بعدی هر یک شامل دو عدد است که دو سر یک یال این زیردرخت است.
2. در سطر اول فایل B.Txt اندازه‌ی کوتاه‌ترین مسیر بین $s_1$ و $t_1$ و در سطر دوم آن اندازه‌ی کوتاه‌ترین مسیر بین $s_2$ و $t_2$‌ را بنویسید.
3. می‌خواهیم راسی مانند $a$ را بیابیم که یک مسیر کمینه از $s_1$ به $t_1$ و یک مسیر کمینه از $s_2$ به $t_2$ موجود باشد که هر دو از $a$‌بگذرد و در ضمن فاصله‌ی $s_1$ و $s_2$ از $a$‌در این مسیر برابر باشد. خروجی این بخش فایل C.Txt است که در سطر اول آن $a$ را می‌نویسید.
4. مسیرهای قسمت قبل را در سطر اول و دوم فایل D.Txt بنویسید. هر مسیر را با دنباله‌ای از رئوس مشخص کنید.

توجه:فرض کنید همه‌ی داده‌ها جواب دارد و لطفا برنامه‌های خود را با داده‌های مختلف امتحان کنید!

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