10263_RoutePlanning

Superior Island is a very picturesque island and only bicycles are allowed on the island. Therefore, there are many one-way bicycle roads connecting the different best photo-shooting spots on the island. To help the visitors plan their trip to the island, the tourism commission wants to designate r different bicycle routes that go through some of the best photo-shooting spots on the island. Given a map of all the bicycle roads on the island and a list of the best photo-shooting spots to be included on each of the three planned routes (non-listed spots must not be included in the route), please write a program to plan each of the r routes so that the distance on each route is minimal. Note that each best photo-shooting spot may only appear at most once on the route.

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