Two solution approaches:

1. Dijkstra's with an appropriate order on vertices
2. 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 ~v~, Dijkstra's prefers the one that has the least cost.
• For this problem, if two paths reach ~v~ 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 ~c~ and number of items picked up ~i~.
• Order the priority queue with respect to the tuple ~(c, -i)~.
• Still standard Dijkstra; runs in ~\mathcal O(V^2)~ or ~\mathcal O(E \log V)~.

Approach 2

• We can simplify the original graph by turning it into a DAG containing only edges on some shortest path from node ~1~ to ~n~.
• Edge ~(a, b)~ with weight ~d~ is in this DAG iff: $$\displaystyle \operatorname{dist}(1, a) + d + \operatorname{dist}(b, n) = \operatorname{dist}(1, n)$$
• This yields a DAG, since if edge ~(a, b)~ is chosen, then ~b~ is strictly closer to ~n~ than ~a~. 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.