Practice: Shortest paths
0 of 4 solved
About these problems
Apply, Connect, Reason and Stretch describe difficulty within this topic, not an official contest rating. Open any problem in any order; reading the chapter first is optional.
- 1Directed travel timesFind shortest distances from vertex 1 to all vertices of a directed nonnegative-weight graph. Print -1 for unreachable vertices.ApplyNot started
- 2Cheapest undirected routeFind the minimum cost from vertex 1 to vertex n in an undirected nonnegative-weight graph. Print -1 if unreachable.ConnectNot started
- 3All-pairs travel deskAnswer minimum-cost queries between pairs of vertices in a small undirected nonnegative-weight graph. Print -1 for an unreachable pair.ReasonNot started
- 4One discounted edgeFind the cheapest directed route from 1 to n if you may discount at most one traversed edge of weight w to floor(w/2). The discount is optional. Print -1 if no route exists.StretchNot started