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

Floyd – yaşama

Floyd – yaşama

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

İstiqamətlənmiş çəkili qraf verilir. Onun əlaqəlilik matrisinə görə hər bir təpələr cütlüyü üçün onlar arasında ən qisa yolun olub olmamasını təyin etmək lazımdır.

Ən qısa yol iki halda olmaya bilər:

  • Heç bir yol yoxdur.

  • Kiçik çəkili istənilən sayda yol var.

Giriş verilənləri

İlk sətirdə qrafın təpələrinin n (1n100) sayı verilir. Qrafın qonşuluq matrisini əks etdirən növbəti n sətrin hər birində n ədəd verilir (i sətrinin j-ci ədədi i təpəsindən j təpəsinə tilin çəkisinə uyğundur). Ondakı 0 ədədi tilin olmadığına işarə edir, istənilən digər ədəd isə uyğun çəkili tilin olduğuna işarə edir. Bütün ədədlər modulca 100-ü aşmır.

Çıxış verilənləri

n ədəd ehtiva edən n sətir verin: i sətrinin j-ci ədədi i-dən j-ə yol olmazsa, 0, ən qısa yol olarsa, 1, kiçik çəkili istənilən sayda yol olarsa, 2 verin.

prb976.gif

Nümunə

Giriş verilənləri #1
5
0 1 2 0 0
1 0 3 0 0
2 3 0 0 0
0 0 0 0 -1
0 0 0 -1 0
Çıxış verilənləri #1
1 1 1 0 0
1 1 1 0 0
1 1 1 0 0
0 0 0 2 2
0 0 0 2 2