1653. Route Planning

输入格式

There are two parts to the input. The first part of input gives the information of the bicycle roads on the island. The first line contains two integer n and r , n <= 100 and r <= 10 , indicating that there are n best photo-shooting spots on the island and there are r routes to be planned. The next n lines (line 2 through line n + 1 ) contains n*n integers (n lines with n integers on each line), where the j -th integer on line i denotes the distance from best photo-shooting spot i - 1 to best photo-shooting spot j ; the distances are all between 0 and 10, where 0 indicates that there is no one-way road going from best photo-shooting spot i - 1 to spot j .

The second part of input has r lines, denoting the r sightseeing routes to be planed. Each line lists the best photo-shooting stops to be included in that route. The integers on each line denote the recommended photo-shooting stops on that particular sightseeing route. The first integer on the line is the starting point of the route and the last integer is the last stop on the route. However, the stops in between can be visited in any order.

输出格式

Output r integers on r lines (one integer per line) indicating the distance of each of the r planned routes. If a route is not possible, output ‘0’.

6 3
0 1 2 0 1 1
1 0 1 1 1 0
0 2 0 1 3 0
4 3 1 0 0 0
0 0 1 1 0 0
1 0 0 0 0 0
1 3 5
6 3 2 5
6 1 2 3 4 5

5
0
7