Reach the Destination with Colored Roads

Given a weighted graph where roads have different costs, return the minimum cost to move from source to destination. Pattern focus: Weighted shortest path. Keep the best known distance to every node and expand the cheapest state next.

Input Format

n = node count, edges = weighted undirected roads [u, v, cost], source = start, target = destination

Output Format

minimum cost to reach the destination

Constraints

  • 1 <= n <= 10^5
  • 1 <= edges.length <= 2 * 10^5
  • 0 <= cost <= 10^9

Examples

Example 1:

Input:

n = 4
edges = [[0,1,2],[1,2,2],[0,2,5],[2,3,1]]
source = 0
target = 3

Output:

5

Explanation:

The cheapest route is 0 -> 1 -> 2 -> 3.

Example 2:

Input:

n = 3
edges = [[0,1,4]]
source = 0
target = 2

Output:

-1

Explanation:

Node 2 is unreachable.

Example 3:

Input:

n = 2
edges = [[0,1,9]]
source = 0
target = 1

Output:

9

Explanation:

A single road gives the answer directly.

Loading...
Reach the Destination with Colored Roads