# TC DrivingAround

Jump to navigation
Jump to search

## Summary[edit]

You are given a directed simple graph with up to 10 nodes, each edge has integer weight between 1 and 5. You need to determine the number of paths from the start node to the end node of a prescribed total weight.

The catch: the total weight can be as big as 10^9.

From TopCoder Single Round Match 342.

## Hints[edit]

- Make an auxiliary graph of some sort.
- Then use repeated squaring of the adjacency matrix.