Problem D
VisuAlgo Online Quiz
VisuAlgo (http://visualgo.net) is a website developed by a team of staff and students of School of Computing, National University of Singapore, the host of the 2015 ACM-ICPC Asia Singapore Regional. VisuAlgo visualizes a number of popular data structures and algorithms in the Computer Science curriculum. Currently, it receives approximately 2000 hits/day from CS students and instructors worldwide.
One new feature of VisuAlgo is
the online quiz. As an example, the above figure shows a
question about the classic Single-Source (Single-Destination)
Shortest Paths problem in graph theory. The beauty of this
online quiz feature is that the question parameters are
randomized. The drawn graph G is taken from a collection of hundreds of
directed weighted graphs (with their 2-D layouts) in
VisuAlgo’s internal database. The
graph G has
However, such randomization of the question parameters may
produce either a trivial question (e.g. “No Answer” when
The developers of VisuAlgo want to calibrate such Shortest Paths question with randomized parameters so that it is possible for a normal Computer Science student to answer the randomly generated question manually within a reasonable amount of time. Please help them.
Input
The first line of input contains two non-negative integers
Thereafter follow
Finally, there are two integers in the last line of input
Output
Print a line with the number of different shortest paths
between
Sample Input 1 | Sample Output 1 |
---|---|
6 10 0 1 26 1 3 29 1 5 9 2 3 25 2 4 43 4 2 3 5 0 13 5 2 33 5 3 18 5 4 58 5 1 |
1 |
Sample Input 2 | Sample Output 2 |
---|---|
7 9 0 1 1 0 2 2 1 2 1 2 3 1 2 4 3 3 4 1 4 5 1 4 6 2 5 6 1 0 6 |
4 |
Sample Input 3 | Sample Output 3 |
---|---|
5 6 0 1 1 1 2 2 2 4 3 0 3 3 3 4 4 0 4 6 0 4 |
2 |