Shortest Path Reachability in a Weighted Graph (with Mandatory Waypoint)

Problem: Shortest Path in a Weighted Graph (with Mandatory Waypoint) You are given a weighted graph G = (V, E) where each edge e(u, v) has a non-negative distance w(u, v). Given a start node S and a target node T: Determine whether T is reachable from S. If reachable, return the shortest distance from S to T; otherwise return -1. Follow-up You are also given a mandatory waypoint node K. The path must go through K (i.e., S -> ... -> K -> ... -> T). If such a path exists, return the minimum distance under this constraint. Otherwise return -1. Input (stdin) n m u1 v1 w1 ... um vm wm S T K n nodes labeled 0..n-1 m edges each edge line: ui vi wi line with S T line with K (ignore if not solving the follow-up) Output (stdout) Print two lines: Line 1: shortest distance from S to T (or -1). Line 2: shortest distance from S to T that must pass K (or -1). Constraints 1 <= n <= 2e5 0 <= m <= 3e5 0 <= wi <= 1e9 graph may be disconnected all weights are non-negative Examples See the 5 test cases in the Chinese version. Example Input 5 6 0 1 2 1 2 3 0 3 10 2 4 1 3 4 2 1 3 2 0 4 1 Output 6 6