TC DrivingAround
From Algorithmist
[edit] Summary
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.
[edit] Hints
- Make an auxiliary graph of some sort.
- Then use repeated squaring of the adjacency matrix.
