Counting PathsGiven a graph as an adjacency matrix, count the total number of paths of length K.
The paths do not have to be simple.
InputTwo integers, N and K (N, K ≤ 100)
An adjacency matrix, N rows of N numbers.
OutputThe number of different paths of length K.
3 1 0 1 1 1 0 1 1 1 0
Note from admin: the test data for this problem is, in particular, erroneous. In certain cases, the answer is too large to be contained in a 32-bit signed integer. However, you should not move to larger data types, and should instead use this type (
int in C/C++,
longint in Pascal) to store the answer and "allow it to overflow" when necessary. Be cautious in other languages where 32-bit signed integers are not the primarily used type.
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 28, 2013
- Graph Theory
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3