eolymp
bolt
Try our new interface for solving problems
Məsələlər

Yolun nömrələnməsi

Yolun nömrələnməsi

Zaman məhdudiyyəti 1 saniyə
Yaddaşı istafadə məhdudiyyəti 128 MiB

Şəhərdəki yolayırıcıları birtərəfli yol ilə birləşdirilmişdir. Hər bir yolayırıcı cütlüyü arasındakı müxtəlif yolların sayını hesablayın. Yolayırıcılarını birləşdirən biristiqamətli yollar ardıcıllığı yol adlanır.

Yolayırıcıları mənfi olmayan tam ədədlərlə işarə olunurlar. Birsitiqamətli yol onun birləşdirdiyi yolayırıcılar cütlüyü ilə işarə edilir. Məsələn, j k onu göstərir ki, biristiqamətli yol j yolayırıcısından k yolayırıcısına gedir. Qeyd edək ki, ikisitiqamətli yol iki biristiqamətli yol ilə modelləşdirilə bilər: j kk j.

Küçələri növbəti şəkildə birləşdirilmiş dörd yolayırıcısı olan şəhərə baxaq:

0 1

0 2

1 2

2 3

01 yolayırıcıları arasında yalnız bir, 02 arasında iki (bu 01202-dir), 03 arasında iki, 12 arasında bir, 13 arasında bir, 23 arasında bir yol var, başqa yollar yoxdur.

Ola bilsin ki, bir neçə yolayırıcı arasında sonsuz sayda yollar olsun. Məsələn, əgər yuxarıda təsvir olunmuş yollar çoxluğuna 3 2 əlavə edilərsə, 01 arasında yalnız bir yol qalacaq, lakin 02 arasında sonsuz sayda yol əmələ gələcək. Ona görə ki, 2-dən 3-ə və 3-dən 2-yə geriyə sonsuz sayda müxtəlif yollarla ixtiyari sayda hərəkət etmək olar. Yəni 0232320232 yolları müxtəlifdir.

Giriş verilənləri

İlk sətir şəhərdəki biristiqamətli küçələrin sayını və ardınca da onların təsvirini ehtiva edir. Hər bir küçə onun birləşdirdiyi yolayırıcılar cütlüyü ilə verilir: hər bir j k cütlüyü j yolayırıcısından k yolayırıcısına qədər biristiqamətli küçəni təmsil edir. Bütün şəhərlərdə yolayırıcıları ardıcıl olaraq 0-dan "ən böyüyünə" qədər nömrələnir. Giriş verilənlərində bütün tam ədədlər boşluqla ayrılmışdır.

Heç bir biristiqamətli küçə yolayırıcısından özünə yol aparmır. Heç bir şəhər 30-dan artıq yolayırıcısına malik deyil.

Çıxış verilənləri

jk yolayırıcıları arasındakı müxtəlif yolların sayı haqqında informasiya ehtiva edən kvadrat matrisi verin. Əgər veriləcək matrisi M ilə işarə edəriksə, onda M[j][k] - j-dən k yolayırıcısına aparan müxtəlif yolların sayıdır. M matrisini sətir-sətir sətirlərin artma ardıcıllığına görə verməli.

Əgər iki yolayırıcısı arasında sonsuz sayda yol olarsa, -1 verməli. Matrisi verərkən çıxış verilənlərini tarazlaşdırmaq üçün narahat olmayın. Matrisin sətirlərindəki veriləcək bütün ədədlər bir boşluqla ayrılmalıdır.

Nümunə

Giriş verilənləri #1
7 0 1 0 2 0 4 2 4 2 3 3 1 4 3
Çıxış verilənləri #1
0 4 1 3 2
0 0 0 0 0
0 2 0 2 1
0 1 0 0 0
0 1 0 1 0
Giriş verilənləri #2
9
0 1 0 2 0 3
0 4 1 4 2 1
2 0
3 0
3 1
Çıxış verilənləri #2
-1 -1 -1 -1 -1
0 0 0 0 1
-1 -1 -1 -1 -1
-1 -1 -1 -1 -1
0 0 0 0 0
Mənbə Летняя Школа 2010, Севастополь, день М.Медведева