UVa 125

From Algorithmist
Jump to navigation Jump to search

Problem Number - Problem Name[edit]

Summary[edit]

Adaption of Floyd-Warshall Floyd-Warshall Algorithm.

Explanation[edit]

For the triple loops in Floyd-Warshall algorithm, if a cycle exists then there exists a k, such that count[i][j] > 0 when i = j.


Input[edit]

7 0 1 0 2 0 4 2 4 2 3 3 1 4 3
5 
0 2 
0 1 1 5 2 5 2 1
9
0 1 0 2 0 3
0 4 1 4 2 1
2 0
3 0
3 1

Output[edit]

matrix for city 0
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
matrix for city 1
0 2 1 0 0 3
0 0 0 0 0 1
0 1 0 0 0 2
0 0 0 0 0 0
0 0 0 0 0 0
0 0 0 0 0 0
matrix for city 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

External links[edit]

Floyd-Warshall Algorithm - Wiki link
, see Categories for a list