Counting Paths
Given a graph as an adjacency matrix, count the total number of paths of length K.The paths do not have to be simple.
Input
Two integers, N and K (N, K ≤ 100)An adjacency matrix, N rows of N numbers.
Output
The number of different paths of length K.Sample Input
3 1 0 1 1 1 0 1 1 1 0
Sample Output
6
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.
All Submissions
Best Solutions
Point Value: 10
Time Limit: 2.00s
Memory Limit: 16M
Added: Jun 28, 2013
Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3
Comments (Search)