Taxi
Time limit2sMemory limit256 MB
Count directed paths from intersection A to B in a one-way road DAG that pass through a given set of required intermediate intersections in any order.
- Level
Hard8 of 10
- Topics
- Graph, Dynamic programming, Topological sort, Combinatorics
- Solved
- No attempts yet
Problem
Seoul has N intersections numbered from 1 to N. Some intersections are connected by narrow one-way roads. In this road network, there is no route that starts from an intersection and returns to the same intersection, and no ordered pair of intersections is connected by more than one road.
Minsung picks up a passenger at intersection A, and the passenger wants to go to intersection B. During the drive, the passenger must visit all of the intersections C1, C2, ..., Ck for meetings. The order in which these intermediate intersections are visited does not matter.
Minsung noticed that there may be several routes satisfying these conditions. Count how many such routes exist.
Input
The first line contains the number of intersections N (1 <= N <= 1,000) and the number of roads M (1 <= M <= 1,000,000).
Each of the next M lines contains the start and end intersections of one road.
After the road data, the input gives the starting intersection A, the destination intersection B, and the number K (0 <= K <= N - 2) of intermediate intersections that must be visited.
Then C1, C2, ..., Ck are given separated by spaces. The intermediate intersections do not include the start or destination, and no intermediate intersection appears more than once.
Output
Print S, the number of routes satisfying the conditions. If no such route exists, print 0.
Inputs where S exceeds 2,000,000,000 are not given.