Description: The PHLHARMONIKER or group in the city of Flute is prepared to Harp City to make a large performance. In the purpose of popular classical music, the orchestra command LYM is ready to take a period of time around some small cities before reaching HARP. In the past few days, musicians will take a flight from a city to another, and finally arrive at the destination HARP (the orchestra can perform more in the same city). Due to the cost of the route and the shift There is a circular flight table between the city and the city. Each time, each direction, the flight table cycle can be different. Now you are looking for a spending table with the smallest spending. Enter: Enter files include a number of Scene. Description of each scene begins with a pair of integers n (2 <= n <= 10) and K (1 <= k <= 1000), and the musicians must patrol in this N cities, and the city uses 1 ..n Number, 1 is the starting point FLUTE city, N is the end of HARP city, next to N * (N-1) flight table, a flight table, describe the route and price between the city, the first A group of N-1 flight tables correspond to flights from cities 1 to other cities (2, 3, ... n), the next N-1 line is from the city 2 to other cities (1, 3, 4 .. The flight is as follows. Each flight is still an integer D (1 <= d <= 30) starts, indicating the cycle of the flight table cycle, the next D non-negative integer represents 1, 2 ... D The price of the two cities in the day, the price is zero means that there is no flight between the two cities that day. For example, "3 75 0 80" means that the first day of the ticket price is 75koi, no flight next day, the third day The ticket is 80koi, then loop: the fourth day is 75koi, there is no flight at the fifth day. The input file ends from N = k = 0 scene. Out: If the group may start from the city 1, every day To another city, finally (after k days) arrive in the city N, then output the minimum of this kaway price. If you can't exist such a tour, output 0. Sample input: 3 6 2 130 150 3 75 0 80 7 120 110 0 100 110 120 0 4 60 70 60 50 3 0 135 140 2 70 80 2 3 2 0 70 1 80 0 0 Sample Output: 460 0
The optimal value of the orchestra in the first place is only related to the first day, in line with the principle of dynamic planning, that is, only associated with the previous state, and one day X-based price is T [ (X-1)% C [L] [J] .Num 1]. We plan to plan with days and locations, A [I] [j] indicates the optimal value of the first city to JU. The Struct array C [11] [11] is used to describe the flight. The price of the city L to city J was C [L] [J] .T [(i-1)% C [L] [j] .num 1]: Dynamic transfer equation is: a [i ] [j] = min {a [i-1] [l] C [l] [j] .t [(i-1)% C [l] [j] .num 1]}; 1 < = L <= N, and C [L] [J] .T [(i-1)% C [L] [J] .NUM 1]! = 0.
Demo procedure:
