UVa 590

From Algorithmist

Contents 1 590 - Always on the run 2 Summary 3 Explanation 4 Input 5 Output

[edit] 590 - Always on the run

• http://acm.uva.es/p/v5/590.html

[edit] 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.

[edit] Explanation

Let cost[a][b] be the cost to travel to city a on b day.

cost[a][b] could be calculated as the minimum of cost[m][b-1] + cost to travel from city m to city a.

[edit] 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

[edit] Output

Scenario #1
The best flight costs 460.

Scenario #2
No flight possible.