UVa 590

From Algorithmist
Jump to navigation Jump to search

590 - Always on the run[edit]

Summary[edit]

A thief wants to find the cheapest way of travelling to a certain city in exactly k days, given that each day she must make exactly one flight.

Explanation[edit]

Letting:

be the minimal cost to travel to city on day
be the cost of the single flight from city to city on day , where denotes a non-existent flight.
be the number of possible cities the thief can escape to (including the currently inhibited one)

We can deduce that:

Which is very similar to the classical UVa 116 problem.

The minimal cost can be calculated quickly using a bottom-up dynamic programming solution.

Input[edit]

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

Output[edit]

Scenario #1
The best flight costs 460.

Scenario #2
No flight possible.