# UVa 590

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.