Loading [MathJax]/jax/output/HTML-CSS/jax.js

المپدیا

دانش‌نامه‌ی المپیاد کامپیوتر ایران

ابزار کاربر

ابزار سایت


سوالات المپیاد:دوره ی تابستان:دوره ی ۸:عملی:سوال ۱۵

کوتاه‌ترین مسیر در گراف

گراف جهت‌دار و وزن‌دار G‌ با n راس داده شده است. برنامه‌ای بنویسید که کوتاه‌ترین مسیر جهت‌دار بین هر دو راس آن را (از نظر مجموع وزن یال‌ها) بیابد.

ورودی

در اولین خط فایل ورودی، n‌و در n خط بعد از آن، ماتریس مجاورت گراف؛ An×n آمده است. درایه‌ی Ai,j نماینده‌ی وزن یال بین راس i ام به راس j‌ ام گراف است. منفی بودن این مقدار نشان‌گر عدم وجود این یال می‌باشد. تمام درایه‌های این ماتریس را قابل ذخیره‌سازی در یک متغیر از نوع Integer فرض کنید.

خروجی

فایل خروجی باید شامل n2‌ خط باشد و در خط (i1)×n+j ام فایل اطلاعات مربوط به کوتاه‌ترین مسیر از راس شماره‌ی i‌به راس با شماره‌ی j را بنویسید:

  • در حالت i=j در این سطر فقط یک صفر بنویسید.
  • در صورت عدم وجود چنین مسیری این سطر باید شامل تنها یک عدد منفی باشد.
  • در غیر از دو حالت بالا، در این سطر نخست تعداد یال‌های مسیر و بعد از آن به‌ترتیب شماره‌ی همه‌ی راس‌های مسیر از i‌ به j را بنویسید.

همه‌ی عددهای فایل خروجی باید قابل ذخیره‌سازی در متغیری از نوع Integer‌ باشند.

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

ورودي نمونه خروجي نمونه
5
0 -1 5 -1 2
1 1 6 -1 -1
-1 3 1 1 4
3 -1 1 0 4
-1 -1 -1 2 0
0
2 1 3 2
3 1 5 4 3
3 1 5 4
1 1 5
1 1 2

ابزار صفحه