Number of Routes Arriving at the Exact Time
Time limit2sMemory limit128 MB
Count the number of routes from S to E in a weighted directed graph that take exactly T minutes, modulo 1,000,003.
- Level
Medium7 of 10
- Topics
- Matrix, Graph, Dynamic programming, Math
- Solved
- No attempts yet
Problem
Sejun is going to the airport to pick up Jeongmun. He has just heard that Jeongmun's flight will arrive T minutes late. Sejun wants to leave his current position, drive around, and arrive at the airport exactly T minutes later.
The intersections and roads are given as an adjacency matrix A. If A[i][j] is 0, there is no direct road from intersection i to intersection j. If A[i][j] is between 1 and 5, there is a road from intersection i to intersection j that takes exactly A[i][j] minutes.
Count the number of routes from the starting point S to the ending point E that arrive in exactly T minutes.
Input
The first line contains four integers: the number of intersections N, the starting point S, the ending point E, and the delay time T. N is a positive integer not greater than 10. S and E are positive integers between 1 and N. T is a positive integer not greater than 1,000,000,000.
The next N lines describe the roads. Each line is a string of N digits, and the j-th digit on the i-th line is A[i][j].
Output
Print the number of routes that start at S and arrive at E exactly T minutes later, modulo 1,000,003.