Problem

9 /10


Floyd - sự tồn tại

Theory Click to read/hide

Con đường xuyên qua chu kỳ trọng lượng âm trở nên bất khả thi.

Problem

Bạn được cung cấp một biểu đồ trọng số có hướng. Sử dụng ma trận kề của nó, bạn cần xác định xem có đường đi ngắn nhất giữa chúng hay không đối với mỗi cặp đỉnh.
 
Nhận xét: Đường đi ngắn nhất có thể không tồn tại vì hai lý do:
  • Không có đường dẫn
  • Có các đường đi có trọng số nhỏ tùy ý
     
Đầu vào
Dòng đầu tiên của tệp đầu vào chứa một số duy nhất: N (1 <=N <=100) — số đỉnh của đồ thị. N dòng tiếp theo chứa N số, mỗi dòng — ma trận kề của đồ thị (số thứ j trong dòng thứ i tương ứng với trọng số của cạnh từ đỉnh i đến đỉnh j): số 0 có nghĩa là không có cạnh và bất kỳ số nào khác — sự hiện diện của một cạnh của trọng số tương ứng. Tất cả các số modulo không vượt quá 100.
 
Đầu ra
In ra N dòng gồm N số. Số thứ j trong dòng thứ i phải tương ứng với đường đi ngắn nhất từ ​​đỉnh i đến đỉnh j. Số phải là 0 nếu không có đường đi, 1 nếu có đường đi ngắn nhất và 2 nếu có đường đi nhưng có các đường đi có trọng số nhỏ tùy ý.

Ví dụ <đầu>

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!

# Đầu vào Đầu ra
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