Find minimum distance in a graph by adding at most one edge

Problem Given a weighted directed graph with a source s and destination t, you may add at most one extra directed edge (from a given set of candidate edges, each with a weight). Find the minimum possible distance from s to t after adding at most one such edge (or none).

Input / Output

• Input: the graph (weighted adjacency list), source s, destination t, and the candidate edges you may add.
• Output: the minimum s -> t distance achievable by adding at most one edge.

Constraints

• Weighted, directed graph; non-negative weights (Dijkstra applies).
• Add at most one additional edge.
• Target complexity: O(E log V).

Example

• If the direct s -> t distance is 20, but adding candidate edge (u, v, 3) gives dist_src[u] + 3 + dist_dst[v] = 12, the answer is 12.