You are given a positive integer n and a 2D integer array edges, where edges[i] = [ui, vi, wi].
There is a weighted connected simple undirected graph with n nodes labeled from 0 to n - 1. Each [ui, vi, wi] in edges represents an edge between node ui and node vi with positive weight wi.
The cost of a path is the sum of weights of the edges in the path, excluding the edge with the maximum weight. If there are multiple edges in the path with the maximum weight, only the first such edge is excluded.
Return an integer representing the minimum cost of a path going from node 0 to node n - 1.
Example 1:
Input: n = 5, edges = [[0,1,2],[1,2,7],[2,3,7],[3,4,4]]
Output: 13
Explanation:
There is only one path going from node 0 to node 4: 0 -> 1 -> 2 -> 3 -> 4.
The edge weights on this path are 2, 7, 7, and 4.
Excluding the first edge with maximum weight, which is 1 -> 2, the cost of this path is 2 + 7 + 4 = 13.
Example 2:
Input: n = 3, edges = [[0,1,1],[1,2,1],[0,2,50000]]
Output: 0
Explanation:
There are two paths going from node 0 to node 2:
0 -> 1 -> 2The edge weights on this path are 1 and 1.
Excluding the first edge with maximum weight, which is 0 -> 1, the cost of this path is 1.
0 -> 2The only edge weight on this path is 1.
Excluding the first edge with maximum weight, which is 0 -> 2, the cost of this path is 0.
The minimum cost is min(1, 0) = 0.
Constraints:
2 <= n <= 5 * 104n - 1 <= edges.length <= 109edges[i] = [ui, vi, wi]0 <= ui < vi < n[ui, vi] != [uj, vj]1 <= wi <= 5 * 104The problem is essentially equivalent to finding a path from node 0 to node n-1, where we have one opportunity to treat the weight of a traversed edge as 0, in order to minimize the sum of path weights.
We first convert edges into an adjacency list g, where g[u] stores all edges (v, w) connected to node u, indicating that there is an edge with weight w between node u and node v.
Next, we use Dijkstra's algorithm to find the shortest path. We define a 2D array dist, where dist[u][0] represents the minimum sum of path weights from node 0 to node u without using the opportunity to treat an edge weight as 0; dist[u][1] represents the minimum sum of path weights from node 0 to node u having already used the opportunity to treat an edge weight as 0.
We use a priority queue pq to store pending nodes. Initially, we enqueue (0, 0, 0), indicating that we start from node 0, with a current path weight sum of 0, and haven't used the opportunity.
In each iteration, we dequeue the node (cur, u, used) with the minimum path weight sum from the priority queue. If the current path weight sum cur is greater than dist[u][used], we skip this node.
If the current node u is node n-1 and we have already used the opportunity used = 1, we return the current path weight sum cur.
For each edge (v, w) of node u, we calculate the path weight sum to reach node v without using the opportunity: nxt = cur + w. If nxt < dist[v][used], we update dist[v][used] and enqueue (nxt, v, used).
If we haven't used the opportunity yet used = 0, we calculate the path weight sum to reach node v when using the opportunity: nxt = cur. If nxt < dist[v][1], we update dist[v][1] and enqueue (nxt, v, 1).
After the traversal ends, we return dist[n-1][1] as the answer.
The time complexity is O(m times log n), and the space complexity is O(n + m), where n and m are the number of nodes and edges, respectively.
Java
C++
Go
TypeScript
Rust
Practice Minimum Distance Excluding One Maximum Weighted Edge with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor