- محدودیت زمان: ۱ ثانیه
- محدودیت حافظه: ۲۵۶ مگابایت
پس از حل سوال قبلی، توک خیلی خوشحال شده است. او می‌خواهد قرار خواستگاری را با آقا تورج هماهنگ کند که ناگهان غافلگیر می‌شود. پشت تلفن، آقا تورج به توک می‌گوید که پوپک خواستگار دیگری به نام صمد دارد ...
آقا تورج برای اینکه بتواند داماد لایقش را انتخاب کند، یک مساله به توک و صمد گفته است که هرکس این مساله را زودتر حل کند، می‌تواند با پوپک ازدواج کند.
آقا تورج فرمانده ارتش است. در راستای انجام پروژه‌ای محرمانه نیاز شده است که $n$ پایگاه ارتش با تعدادی تونل دوطرفه یه یکدیگر متصل شوند، ارتش می‌تواند بین هر دو پایگاه دلخواه $i$ و $j$ تونلی بسازد که طول آن عددی بین $1$ تا $10^9$ (شامل هر دو) باشد.
ارتش می‌خواهد که این تونل‌ها را به شکلی بین برخی از پایگاه‌ها بسازد که در نهایت طول کوتاه‌ترین مسیر از پایگاه $i$ به پایگاه $j$ برابر با $A_{i, j}$ باشد.
آقا تورج می‌خواهد ببیند که آیا می‌توان تونل‌هایی ساخت که شرایط بالا برقرار باشد یا نه. اگر می‌توان به شکلی تونل‌ها را بین پایگاه‌ها ساخت که شرایط برقرار باشد، کمینه تعداد تونل‌های مورد نیاز چقدر است؟
توک و صمد پس از شنیدن مساله هر دو دست به کار می‌شوند ... اما ای دل غافل که این صمد است که خیلی زود پاسخ را به آقا تورج می‌گوید و توک از رسیدن به مرادش باز می‌ماند. توک که دیگر عصبانی شده است و افکار پلیدی در سر دارد می‌خواهد ببیند که جوابی که صمد به آقا تورج داده است چه بوده است. برای این‌کار از شما کمک می‌گیرد ...
ورودی
در خط اول ورودی عدد $n$ ، تعداد پایگاه‌های ارتش آمده است.
سپس در $n$ سطر بعدی ماتریس $A$ می‌آید.
در هر سطر $n$ عدد می‌آید که عدد $j$ ام در سطر $i+1$ ام ورودی ، طول کوتاه‌ترین مسیر از پایگاه $i$ به $j$ را مشخص می‌کند، تضمین می‌شود که $A_{i, i} = 0$ است.
$$1 \le n \le 500$$ $$i \neq j : 1 \le A_{i, j} \le 10^9$$ $$ i = j : A_{i, j} = 0 $$
خروجی
چناچه نمی‌توان تعدادی تونل دوطرفه با طول‌های دلخواه ساخت که طول کوتاه‌ترین مسیر از پایگاه $i$ به پایگاه $j$ برابر با $A_{i, j}$ باشد، در یک خط فقط عدد -1 را چاپ کنید .
در غیراین‌صورت کمترین تعداد تونل مورد نیاز که باید بین پایگاه‌ها ساخته شود را چاپ کنید.
مثال
ورودی نمونه ۱
2
0 4
4 0
خروجی نمونه ۱
1
کافی است یه تونل با طول $4$ (زمان گذشتن از آن $4$ است) ، بین پایگاه‌های $1$ و $2$ بسازیم.
ورودی نمونه ۲
1
0
خروجی نمونه ۲
0
ورودی نمونه ۳
2
0 10
56 0
خروجی نمونه ۳
-1
نمی‌توان تعدادی تونل ساخت که طول کوتاه‌ترین مسیر از پایگاه $1$ به $2$ با طول کوتاه‌ترین مسیر از پایگاه $2$ به $1$ برابر نباشد (تونل‌ها همگی دوطرفه‌اند)
ورودی نمونه ۴
3
0 4 8
4 0 4
8 4 0
خروجی نمونه ۴
2
ارسال پاسخ برای این سؤال