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

Problem Types: [Show]

Languages Allowed:
C++03, PAS, C, HASK, ASM, RUBY, PYTH2, JAVA, PHP, SCM, CAML, PERL, C#, C++11, PYTH3

Comments (Search)

Is the weight always going to be 1 or 0?

where does it say weight?

You may assume this graph is unweighted.