Module: Algoritma Floyd


Problem

9 /10


Floyd - kewujudan

Theory Click to read/hide

Laluan melalui kitaran berat negatif menjadi mustahil.

Problem

Anda diberi graf berwajaran terarah. Menggunakan matriks bersebelahan, anda perlu menentukan untuk setiap pasangan bucu sama ada terdapat laluan terpendek di antara mereka atau tidak.
 
Ulasan: Laluan terpendek mungkin tidak wujud atas dua sebab:
  • Tiada laluan
  • Terdapat laluan dengan berat kecil sewenang-wenangnya
     
Input
Baris pertama fail input mengandungi satu nombor: N (1 <=N <=100) — bilangan bucu graf. N baris seterusnya mengandungi N nombor setiap satu — matriks bersebelahan graf (nombor ke-j dalam baris ke-i sepadan dengan berat tepi dari bucu i ke bucu j): nombor 0 bermakna tiada tepi, dan sebarang nombor lain — kehadiran tepi berat yang sepadan. Semua nombor modulo tidak melebihi 100.
 
Output
Cetak N baris N nombor. Nombor ke-j dalam baris ke-i mesti sepadan dengan laluan terpendek dari bucu i ke bucu j. Nombornya hendaklah 0 jika tiada laluan, 1 jika terdapat laluan terpendek, dan 2 jika terdapat laluan tetapi terdapat laluan yang beratnya kecil sewenang-wenangnya.

Contoh

time 1000 ms
memory 256 Mb
Rules for program design and list of errors in automatic problem checking

Teacher commentary

Your Program

Attach a file with the source code of the program:

or select a programming language and type your program

Auto

       

Program check result To check the solution of the problem, you need to register or log in!

# Input Output
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 
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