Graph Contest 1 P1 - Counting Paths - Olympiads Online Judge

Graph Contest 1 P1 - Counting Paths

View as PDF

Submit solution

All submissions

Best submissions

Points: 10

Time limit: 1.0s

Memory limit: 16M

Problem type

Given a graph as an adjacency matrix, count the total number of paths of length $K$ $K$ .
The paths do not have to be simple.

Input Specification

Two integers, $N$ $N$ and $K$ $K$ $(N, K \le 100)$ $(N, K \leq 100)$ .
An adjacency matrix, $N$ $N$ rows of $N$ $N$ numbers.

Output Specification

The number of different paths of length $K$ $K$ .

Sample Input

Copy

Sample Output

Copy

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.

Comments

1

Genius3435 commented on June 13, 2021, 10:43 p.m.

I seem to be getting WA on test 5, and when I look at the output, it shows a negative number. Is this a problem with my algorithm or with using signed integers?

1

Dingledooper commented on June 13, 2021, 11:08 p.m.

It's just a minor bug which causes your code to fail for $K = 100$ $K = 100$ .

1

Genius3435 commented on June 14, 2021, 5:22 a.m.

Thanks, it works now!