المپدیا

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

ابزار کاربر

ابزار سایت


سوالات المپیاد:متفرقه:آزمون های اینترنتی ۸۹ تا ۹۱:سوال ۳۲

Distace Matrix

‎Distance Matrix‎ یک گراف ‎$n$‎ راسی، یک ماتریس ‎$n \times n$‎ است که درایه ‎$(i,j)$‎ آن برابر فاصله دو راس ‎$i$‎ام و ‎$j$‎ام آن است. ‎ ‎Distance Matrix‎ یک گراف وزن‌دار همبند ‎$n$‎ راسی که وزن تمام یال‌های آن بیش‌تر یا مساوی $1$‎ است به شما داده شده است. شما باید کم‌ترین ‎$x$‎ را به‌دست بیاورید که مجموع وزن یال‌های گراف متناظر با آن می‌تواند ‎$x$‎ باشد.‎

ورودی

  • در سطر اول ورودی عدد ‎$1 \leq n \leq 50$‎ آمده است.
  • در ‎$n$‎ سطر بعدی، در هر سطر ‎$n$‎ عدد آمده است که ماتریس را مشخص می‌کنند.‎
  • تمامی اعداد ورودی بین $0$‎ تا ‎$2500$‎ اند.‎

خروجی

  • در صورتی که هیچ گرافی وجود ندارد که ‎Distance Matrix‎ آن برابر ماتریس ورودی باشد در خروجی ‎$-1$‎ چاپ نمایید.
  • در غیر این‌صورت ‎$x$‎ را در خروجی چاپ نمایید.‎

محدودیت‌ها

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

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

ورودی نمونه خروجی نمونه
3‎
0 2 2‎
2 0 2‎
2 2 0
6
5‎
0 6 15 2 6‎
6 0 9 8 12‎
15 9 0 16 18‎
2 8 16 0 4‎
‎6 12 18 4 0
55

ابزار صفحه