GPS I Love You#2680
Thomas T. Garmin got a GPS for his birthday last year, and he loved it! Unfortunately, sometimes Tom wanted to take a scenic route rather than the shortest one as suggested by the GPS. He did a little reading in the manual and discovered that the GPS algorithm could be overridden by specifying roads which the GPS system would be forced to use when determining a route. After some experimentation, Tom found that often, forcing a single road was enough to get the desired route. However, for some more complicated routes, Tom needed to force the GPS to use more roads. Eventually, Tom began to worry that he was wasting too much time picking roads to force before each trip. Now, instead of enjoying his GPS, he spends his drives pondering the following question: could he have made the GPS select the scenic route using fewer forced roads?
Can you save this love affair, or are Tom and his GPS doomed to go their separate ways?
Input for each test case consists of several lines. The first line contains a single integer n < 100 indicating the number of endpoints for the roads, numbered through n-1. There will then follow lines each containing non-negative integers. If the -th value in row is positive, it indicates the length of a road from endpoint to endpoint ; if the value is , it indicates that there is no road between those two endpoints. After these lines, there will be a line of the form m\ p_1\ p_2\ p_{3}\ \ldots\ p_m specifying the scenic route Tom wants: the route contains m-1 roads and goes between endpoints p_1 and p_m, visiting endpoints p_2, p_3, etc., in that order. The last test case will be followed by a line containing .
Note that when Tom specifies his forced roads to the GPS, he specifies both their direction and order. All routes are simple paths, and all road lengths are .
For each test case, output one line as follows:
Case n: k
where is the smallest number of roads Tom must force such that the GPS will choose the specified route. You should assume that if there are multiple shortest paths, the GPS always selects the most scenic of these. Therefore, if Tom's route is among the shortest to use a given set of forced roads, it will be picked by the GPS.
Example 1