|
If I'm reading the problem statement right, it's just a single-source shortest paths problem in a positive weights graph. You can solve this with Dijkstra's algorithm. The algorithm does use dynamic programming, but I don't really consider it very representative of how dynamic programming problems look like in competition programming.
However, in it's own right, the algorithm is important enough for you to get very familiar with it because it is useful for solving many problems. |