For emergency supply routing, roads have different travel costs, and Lamia needs both the shortest cost AND the actual route from the depot to the affected zone. Given a weighted directed graph with N nodes and M edges (non-negative weights), a source S, and a target T, print the shortest distance from S to T AND one valid shortest path (sequence of nodes). Use a priority-queue-based Dijkstra for O((N+M) log N); N and M can be up to 2×10^5.
Input
Line1: N M S T. Next M lines: u v w.
Output
Line1: shortest distance, or -1 if unreachable. Line2 (if reachable): the path, space-separated node ids.
Constraints
1 ≤ N ≤ 2×10^5, 0 ≤ M ≤ 2×10^5, 0 ≤ w ≤ 10^4
Sample Input
4 4 1 4 1 2 1 2 3 2 3 4 1 1 4 10
Sample Output
4 1 2 3 4
main.c
Loading editor…
Write C, then Run (custom I/O) or Submit (sample tests). ⌘/Ctrl+Enter submits.