LA 2730

From Algorithmist
Jump to navigation Jump to search

LA 2730 - Toll[edit]

Summary[edit]

You have to travel from one place to another via a network of cities and villages. You are supposed to bring P items into the destination place. Each time you enter a village, you have to pay 1 item for entering it, each time you enter a city you have to pay 1 item per each 20 items you brought in (rounded up). Find the smallest amount of items you should have at the beginning of your journey.

Explanation[edit]

This is just a concealed Dijkstra's algorithm. For each location compute the smallest number of items sufficient to get from there to the destination. Note that the algorithm has to be run "backwards", from the location where you end your journey.

For this problem the reverse method is also applicable (Bellman-Ford) when finding minimum cost from destination point with initially spoons (consumption) to the starting location.

Notes[edit]

  • It is guaranteed that the underlying graph contains a path from your starting place to your destination.

Implementations[edit]

The input graph is small (), there is no need to implement any fancy optimizations. The expected running time of algorithm is .

Input[edit]

1
a Z
19 a Z
5
A D
D X
A b
b c
c X
39 A X
-1

Output[edit]

Case 1: 20
Case 2: 44