## Editorial for ICPC NAQ 2016 C - Big Truck

Remember to use this editorial

**only**when stuck, and**not to copy-paste code from it**. Please be respectful to the problem author and editorialist.**Submitting an official solution before solving the problem yourself is a bannable offence.**Two solution approaches:

- Dijkstra's with an appropriate order on vertices
- Longest path in a directed acyclic graph

#### Approach 1

- All edge weights are positive, so Dijkstra's algorithm will easily find shortest paths. The graph is small enough that sparse or dense Dijkstra will both work.
- Whenever two paths reach vertex , Dijkstra's prefers the one that has the least cost.
- For this problem, if two paths reach with the same minimum cost, then we break the tie with the path which has picked up the most items thus far.
- For each path, keep two pieces of information: path cost and number of items picked up .
- Order the priority queue with respect to the tuple .
- Still standard Dijkstra; runs in or .

#### Approach 2

- We can simplify the original graph by turning it into a DAG containing only edges on some shortest path from node to .
- Edge with weight is in this DAG iff:
- This yields a DAG, since if edge is chosen, then is strictly closer to than . So, there can't be any cycles.
- The problem reduces to finding the longest path in this DAG, with length defined by the number of items at each vertex. This can be solved in linear time using dynamic programming.

## Comments