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.
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