# UVa 590

## Summary

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

Letting:

 ${\displaystyle minCost[a][b]}$ be the minimal cost to travel to city ${\displaystyle a}$ on ${\displaystyle b}$ day ${\displaystyle flightCost(i,j,d)}$ be the cost of the single flight from city ${\displaystyle i}$ to city ${\displaystyle j}$ on day ${\displaystyle d}$, where ${\displaystyle flightCost(i,j,d)=0}$ denotes a non-existent flight. ${\displaystyle n}$ be the number of possible cities the thief can escape to (including the currently inhibited one)

We can deduce that:

${\displaystyle minCost[a][b]=min(minCost[i][b-1]+flightCost(i,a,b)),\forall i:1\leq i\leq n,i\neq a,flightCost(i,a,b)\neq 0}$

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

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

Scenario #1
The best flight costs 460.

Scenario #2
No flight possible.