3778. Minimum Distance Excluding One Maximum Weighted Edge 🔒

Medium

LeetCode ↗

Problem Pattern Idea Example Code Complex Pitfalls

Problem Description

You are given a positive integer n and a 2D integer array edges, where each edges[i] = [u_i, v_i, w_i].

There is a weighted, connected, simple, undirected graph with n nodes labeled from 0 to n - 1. Each entry [u_i, v_i, w_i] in edges represents an edge between node u_i and node v_i with a positive weight w_i.

The cost of a path is defined as the sum of the weights of the edges in that path, but excluding the edge with the maximum weight. If there are multiple edges in the path that share the maximum weight, only the first such edge is excluded from the sum.

Your task is to return an integer representing the minimum cost of a path traveling from node 0 to node n - 1.

In other words, you want to find a path from node 0 to node n - 1 where you are allowed to drop the largest-weight edge along the way (counting its weight as 0), and you want to choose the path so that the resulting total weight is as small as possible.

Quick Interview Experience

Help others by sharing your interview experience

Have you seen this problem before?

How We Pick the Algorithm

Why Dijkstra's Algorithm?

This problem maps to Dijkstra's Algorithm through a short path in the full flowchart.

Finding the minimum-cost path from node 0 to n-1 with the option to skip one maximum-weight edge is a stateful shortest path problem solved by Dijkstra.

Open in Flowchart

Intuition

The key observation is that "excluding the edge with the maximum weight" is the same as being allowed to make one edge along the path free (its weight becomes 0).

Why? Suppose we have already fixed a path. The cost is the sum of all edge weights minus the largest one. To minimize the cost over all paths, we want this "free" edge to ideally be the largest edge on the path. But notice that if we simply give ourselves the freedom to zero out any one edge on the chosen path, the optimal choice will always naturally fall on the edge with the maximum weight — because zeroing out the heaviest edge removes the most weight. So instead of explicitly tracking which edge is the maximum, we can just allow ourselves one chance to set any single edge's weight to 0, and the optimization will take care of selecting the best edge to drop.

This transforms the problem into: find the shortest path from node 0 to node n - 1, where along the way we have exactly one opportunity to traverse an edge for free.

This is a classic shortest path with a state problem, perfectly suited for Dijkstra's algorithm. The twist is that the state of each node is no longer just "where we are," but also "whether we have already used our one free-edge opportunity." So we expand each node into two states:

dist[u][0]: the minimum total weight to reach node u without having used the free opportunity yet.
dist[u][1]: the minimum total weight to reach node u having already used the free opportunity.

From any node in state 0, we have two choices when crossing an edge (v, w):

Pay the full weight w and stay in state 0, moving to dist[v][0].
Use our free opportunity here, paying 0, and move into state 1 at dist[v][1].

Once we are in state 1, the opportunity is gone, so every edge must be paid in full and we remain in state 1.

By running Dijkstra over this expanded graph of 2n states, the first time we settle node n - 1 in state 1 gives us the answer — the minimum cost path where exactly one (optimally the heaviest) edge has been excluded.

Solution Approach

We solve this using Dijkstra's Algorithm over an expanded state space.

Step 1: Build the adjacency list.

We first convert edges into an adjacency list g, where g[u] stores all edges (v, w) connected to node u, indicating there is an edge with weight w between node u and node v. Since the graph is undirected, each edge [u, v, w] is added to both g[u] and g[v].

g = [[] for _ in range(n)]
for u, v, w in edges:
    g[u].append((v, w))
    g[v].append((u, w))

Step 2: Define the distance array with the extra state.

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.

All values are initialized to infinity, except dist[0][0] = 0, since we begin at node 0 with cost 0 and no opportunity used.

Step 3: Run Dijkstra with a priority queue.

We use a priority queue (min-heap) pq to store pending nodes as tuples (cur, u, used), where cur is the current accumulated path weight, u is the current node, and used is whether the free opportunity has been used. Initially we push (0, 0, 0).

In each iteration, we pop the tuple (cur, u, used) with the smallest path weight from the heap. If cur > dist[u][used], this entry is outdated, so we skip it.

cur, u, used = heappop(pq)
if cur > dist[u][used]:
    continue

Step 4: Early termination.

If the current node u is node n - 1 and we have already used the opportunity (used == 1), then because Dijkstra always pops the smallest path weight first, the current cur is guaranteed to be the minimum cost. We return it immediately.

if u == n - 1 and used:
    return cur

Step 5: Relax neighboring edges.

For each edge (v, w) of node u, we consider two transitions:

Pay the full weight. Compute nxt = cur + w. If nxt < dist[v][used], update dist[v][used] and push (nxt, v, used) onto the heap. This keeps the same used state.
Use the free opportunity (only valid if used == 0). Compute nxt = cur (the edge costs nothing). If nxt < dist[v][1], update dist[v][1] and push (nxt, v, 1). This transitions us into the "opportunity used" state.

for v, w in g[u]:
    nxt = cur + w
    if nxt < dist[v][used]:
        dist[v][used] = nxt
        heappush(pq, (nxt, v, used))
    if used == 0:
        nxt = cur
        if nxt < dist[v][1]:
            dist[v][1] = nxt
            heappush(pq, (nxt, v, 1))

Step 6: Return the answer.

After the traversal ends, dist[n - 1][1] holds the minimum cost of reaching node n - 1 after using the free opportunity, which is returned as the answer.

Complexity Analysis.

Let m be the number of edges. The expanded graph has 2n states and each edge is relaxed for both states, so there are O(m) edges in the expanded graph. The time complexity is O(m log m) due to the heap operations, and the space complexity is O(n + m) for the adjacency list, distance array, and priority queue.

Example Walkthrough

Let's trace through the solution approach using a small example.

Input:

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

We want the minimum cost path from node 0 to node 3, where we may drop the single heaviest edge along the chosen path.

Step 1: Build the adjacency list.

g[0] = [(1, 4), (2, 2)]
g[1] = [(0, 4), (3, 5)]
g[2] = [(0, 2), (3, 7)]
g[3] = [(1, 5), (2, 7)]

Step 2: Initialize the distance array.

Each node has two states: [without free used, with free used]. All start at infinity except dist[0][0] = 0.

dist[0] = [0, ∞]
dist[1] = [∞, ∞]
dist[2] = [∞, ∞]
dist[3] = [∞, ∞]

The heap starts with (0, 0, 0) — cost 0, at node 0, free opportunity unused.

Step 3–5: Run Dijkstra.

Pop (0, 0, 0). Node 0, used = 0. Relax both neighbors:

Edge (1, 4):
- Pay full: nxt = 0 + 4 = 4 → update dist[1][0] = 4, push (4, 1, 0).
- Use free: nxt = 0 → update dist[1][1] = 0, push (0, 1, 1).
Edge (2, 2):
- Pay full: nxt = 0 + 2 = 2 → update dist[2][0] = 2, push (2, 2, 0).
- Use free: nxt = 0 → update dist[2][1] = 0, push (0, 2, 1).

Pop (0, 1, 1). Node 1, used = 1 (free already spent). Not node 3, so continue. Relax:

Edge (0, 4): nxt = 0 + 4 = 4, but dist[0][1] = ∞, so update to 4, push (4, 0, 1).
Edge (3, 5): nxt = 0 + 5 = 5 → update dist[3][1] = 5, push (5, 3, 1).

Pop (0, 2, 1). Node 2, used = 1. Relax:

Edge (0, 2): nxt = 0 + 2 = 2, dist[0][1] = 4 > 2, so update dist[0][1] = 2, push (2, 0, 1).
Edge (3, 7): nxt = 0 + 7 = 7, dist[3][1] = 5 < 7, no update.

Pop (2, 0, 1). Node 0, used = 1. Relax (everything reachable already cheaper), no improvements.

Pop (2, 2, 0). Node 2, used = 0. Relax:

Edge (0, 2): full 4 > dist[0][0] = 0; free nxt = 2 > dist[0][1] = 2, no update.
Edge (3, 7): full nxt = 2 + 7 = 9 > dist[3][0]=∞, update dist[3][0]=9; free nxt = 2, dist[3][1] = 5 < 2? No, 2 < 5 so update dist[3][1] = 2, push (2, 3, 1).

Pop (2, 3, 1). Node 3 and used = 1 → early termination triggers. Return cur = 2.

Why this is optimal.

The chosen path is 0 → 2 → 3 with weights 2 and 7. The heaviest edge (7) is dropped for free, leaving cost 2. Compare to the alternative path 0 → 1 → 3 (weights 4, 5): dropping the heaviest (5) leaves cost 4. The algorithm correctly settles on the cheaper option, 2.

Final answer: 2.

Solution Implementation

1from typing import List
2from heapq import heappush, heappop
3from math import inf
4
5
6class Solution:
7    def minCostExcludingMax(self, n: int, edges: List[List[int]]) -> int:
8        # Build an undirected adjacency list:
9        # graph[node] = list of (neighbor, weight)
10        graph: List[List[tuple[int, int]]] = [[] for _ in range(n)]
11        for u, v, w in edges:
12            graph[u].append((v, w))
13            graph[v].append((u, w))
14
15        # dist[node][used] = minimum cost to reach `node`
16        #   used = 0 -> the "free edge" option is still available
17        #   used = 1 -> the "free edge" option has already been consumed
18        dist: List[List[float]] = [[inf] * 2 for _ in range(n)]
19        dist[0][0] = 0
20
21        # Min-heap of (current_cost, node, used)
22        priority_queue: List[tuple[int, int, int]] = [(0, 0, 0)]
23
24        while priority_queue:
25            cost, node, used = heappop(priority_queue)
26
27            # Skip stale entries that are worse than the best known distance.
28            if cost > dist[node][used]:
29                continue
30
31            # If we reached the target and have already used the free edge,
32            # this is guaranteed to be the optimal answer (Dijkstra property).
33            if node == n - 1 and used:
34                return cost
35
36            for neighbor, weight in graph[node]:
37                # Option 1: traverse this edge normally (pay its weight).
38                next_cost = cost + weight
39                if next_cost < dist[neighbor][used]:
40                    dist[neighbor][used] = next_cost
41                    heappush(priority_queue, (next_cost, neighbor, used))
42
43                # Option 2: if the free option is still available, use it on
44                # this edge (skip paying its weight) and mark used = 1.
45                if used == 0:
46                    next_cost = cost  # no weight added
47                    if next_cost < dist[neighbor][1]:
48                        dist[neighbor][1] = next_cost
49                        heappush(priority_queue, (next_cost, neighbor, 1))
50
51        # Reaching here means the target's "free edge used" state was finalized
52        # without an early return; return that best cost.
53        return dist[n - 1][1]
54

1class Solution {
2    public long minCostExcludingMax(int n, int[][] edges) {
3        // Build an adjacency list for the undirected weighted graph.
4        // Each entry stores {neighbor, weight}.
5        List<int[]>[] graph = new ArrayList[n];
6        Arrays.setAll(graph, key -> new ArrayList<>());
7        for (int[] edge : edges) {
8            int from = edge[0];
9            int to = edge[1];
10            int weight = edge[2];
11            graph[from].add(new int[] {to, weight});
12            graph[to].add(new int[] {from, weight});
13        }
14
15        // A large sentinel value used as "infinity" to avoid overflow during addition.
16        long infinity = Long.MAX_VALUE / 4;
17
18        // dist[node][state] is the minimum cost to reach `node` where:
19        //   state = 0 -> no edge has been skipped (excluded) yet
20        //   state = 1 -> exactly one edge has already been skipped (its cost ignored)
21        long[][] dist = new long[n][2];
22        for (int i = 0; i < n; i++) {
23            dist[i][0] = infinity;
24            dist[i][1] = infinity;
25        }
26        dist[0][0] = 0;
27
28        // Dijkstra over an expanded state space (node, skipUsed).
29        // Each element in the queue is {currentCost, node, skipUsed}.
30        PriorityQueue<long[]> pq =
31                new PriorityQueue<>(Comparator.comparingLong(state -> state[0]));
32        pq.add(new long[] {0, 0, 0});
33
34        while (!pq.isEmpty()) {
35            long[] top = pq.poll();
36            long currentCost = top[0];
37            int node = (int) top[1];
38            int skipUsed = (int) top[2];
39
40            // Skip stale entries that have already been improved.
41            if (currentCost > dist[node][skipUsed]) {
42                continue;
43            }
44
45            // Reaching the last node with the skip already used yields the answer.
46            if (node == n - 1 && skipUsed == 1) {
47                return currentCost;
48            }
49
50            for (int[] adjacent : graph[node]) {
51                int next = adjacent[0];
52                int weight = adjacent[1];
53
54                // Option 1: traverse this edge normally, paying its weight.
55                long normalCost = currentCost + weight;
56                if (normalCost < dist[next][skipUsed]) {
57                    dist[next][skipUsed] = normalCost;
58                    pq.add(new long[] {normalCost, next, skipUsed});
59                }
60
61                // Option 2: if no edge has been skipped yet, skip this edge's cost.
62                // This moves us into state 1 without adding the edge weight.
63                if (skipUsed == 0) {
64                    long skippedCost = currentCost;
65                    if (skippedCost < dist[next][1]) {
66                        dist[next][1] = skippedCost;
67                        pq.add(new long[] {skippedCost, next, 1});
68                    }
69                }
70            }
71        }
72
73        // Fallback: shortest cost to the destination with one edge skipped.
74        return dist[n - 1][1];
75    }
76}
77

1class Solution {
2public:
3    long long minCostExcludingMax(int n, vector<vector<int>>& edges) {
4        // Build an undirected weighted adjacency list.
5        // adjacency[node] holds pairs of (neighbor, weight).
6        vector<vector<pair<int, int>>> adjacency(n);
7        for (auto& edge : edges) {
8            int from = edge[0], to = edge[1], weight = edge[2];
9            adjacency[from].push_back({to, weight});
10            adjacency[to].push_back({from, weight});
11        }
12
13        // A large sentinel value representing "unreachable".
14        // Divided by 4 to avoid overflow when summing edge weights.
15        const long long INF = LLONG_MAX / 4;
16
17        // distance[node][skipUsed] = minimum cost to reach `node`,
18        // where skipUsed == 0 means we have NOT yet skipped an edge's cost,
19        // and skipUsed == 1 means we already used our one free skip.
20        vector<array<long long, 2>> distance(n, {INF, INF});
21        distance[0][0] = 0;
22
23        // Min-heap ordered by accumulated cost.
24        // Each entry is {cost, node, skipUsed}.
25        priority_queue<
26            array<long long, 3>,
27            vector<array<long long, 3>>,
28            greater<array<long long, 3>>
29        > minHeap;
30        minHeap.push({0, 0, 0});
31
32        while (!minHeap.empty()) {
33            auto top = minHeap.top();
34            minHeap.pop();
35
36            long long currentCost = top[0];
37            int node = static_cast<int>(top[1]);
38            int skipUsed = static_cast<int>(top[2]);
39
40            // Skip stale heap entries that have been superseded
41            // by a cheaper path already finalized.
42            if (currentCost > distance[node][skipUsed]) {
43                continue;
44            }
45
46            // We reached the target having already used the free skip;
47            // because Dijkstra pops states in non-decreasing cost order,
48            // this is guaranteed to be the optimal answer.
49            if (node == n - 1 && skipUsed == 1) {
50                return currentCost;
51            }
52
53            // Relax all neighboring edges.
54            for (auto [neighbor, weight] : adjacency[node]) {
55                // Option 1: traverse the edge and pay its weight.
56                long long nextCost = currentCost + weight;
57                if (nextCost < distance[neighbor][skipUsed]) {
58                    distance[neighbor][skipUsed] = nextCost;
59                    minHeap.push({nextCost, neighbor, skipUsed});
60                }
61
62                // Option 2: if we still have our free skip available,
63                // traverse this edge for free (skip its cost) and mark
64                // the skip as consumed.
65                if (skipUsed == 0) {
66                    long long freeCost = currentCost;
67                    if (freeCost < distance[neighbor][1]) {
68                        distance[neighbor][1] = freeCost;
69                        minHeap.push({freeCost, neighbor, 1});
70                    }
71                }
72            }
73        }
74
75        // Fallback: return the best cost to the target with the skip used.
76        return distance[n - 1][1];
77    }
78};
79

1/**
2 * Finds the minimum path cost from node 0 to node n-1 while allowing
3 * exactly one edge along the path to be excluded (treated as cost 0).
4 * Uses a state-expanded Dijkstra: each node carries a flag indicating
5 * whether the free-edge skip has already been used.
6 */
7function minCostExcludingMax(n: number, edges: number[][]): number {
8    // Adjacency list: graph[node] = list of [neighbor, weight]
9    const graph: [number, number][][] = Array.from({ length: n }, () => []);
10    for (const [from, to, weight] of edges) {
11        graph[from].push([to, weight]);
12        graph[to].push([from, weight]); // Undirected edge
13    }
14
15    const INF = Infinity;
16
17    // dist[node][skipUsed]:
18    //   skipUsed = 0 -> shortest cost reaching `node` without skipping any edge
19    //   skipUsed = 1 -> shortest cost reaching `node` having skipped one edge
20    const dist: number[][] = Array.from({ length: n }, () => [INF, INF]);
21    dist[0][0] = 0;
22
23    // Min-heap ordered by cost, tie-broken by node index.
24    // Each entry: [cost, node, skipUsed]
25    const pq = new PriorityQueue<[number, number, number]>((a, b) =>
26        a[0] === b[0] ? a[1] - b[1] : a[0] - b[0],
27    );
28
29    pq.enqueue([0, 0, 0]);
30
31    while (pq.size() > 0) {
32        const [cost, node, skipUsed] = pq.dequeue()!;
33
34        // Skip stale entries that were already improved.
35        if (cost > dist[node][skipUsed]) {
36            continue;
37        }
38
39        // Reached the destination with the skip already consumed: optimal answer.
40        if (node === n - 1 && skipUsed === 1) {
41            return cost;
42        }
43
44        for (const [next, weight] of graph[node]) {
45            // Option 1: traverse this edge normally, paying its weight.
46            const costNormal = cost + weight;
47            if (costNormal < dist[next][skipUsed]) {
48                dist[next][skipUsed] = costNormal;
49                pq.enqueue([costNormal, next, skipUsed]);
50            }
51
52            // Option 2: if no edge has been skipped yet, skip this one (cost stays the same).
53            if (skipUsed === 0) {
54                const costSkipped = cost;
55                if (costSkipped < dist[next][1]) {
56                    dist[next][1] = costSkipped;
57                    pq.enqueue([costSkipped, next, 1]);
58                }
59            }
60        }
61    }
62
63    // Fallback: best cost reaching the destination with the skip used.
64    return dist[n - 1][1];
65}
66

Time and Space Complexity

Time Complexity: O(m × log n), where n and m are the number of nodes and edges respectively.

This is a Dijkstra-style shortest path algorithm running on a state-expanded graph. The state space consists of 2 × n states, since each node u is paired with a binary flag used ∈ {0, 1} indicating whether one edge weight has been waived (the "excluding max" relaxation that sets nxt = cur). The graph is built with adjacency lists, so each edge (u, v, w) is stored twice (once for each direction), giving O(m) total adjacency entries.

During the Dijkstra traversal, each edge can be processed in both layers (used = 0 and used = 1), so the total number of edge relaxations is O(2m) = O(m). Each relaxation may trigger a heappush, and each pop from the priority queue costs O(log) of the heap size. Since the heap holds states bounded by 2n, each heap operation costs O(log n). Combining the relaxations with the logarithmic heap operations yields an overall time complexity of O(m × log n).
Space Complexity: O(n + m), where n and m are the number of nodes and edges respectively.

The adjacency list g stores every edge twice, consuming O(n + m) space. The dist array holds two states per node, requiring O(2n) = O(n) space. The priority queue pq may contain up to O(m) entries in the worst case (since each relaxation can push a new entry). Summing these contributions gives a total space complexity of O(n + m).

Common Pitfalls

Pitfall 1: Returning `dist[n - 1][0]` instead of `dist[n - 1][1]`

A very common mistake is to return the wrong distance state at the end. Since the problem requires dropping the maximum-weight edge along the path, the answer must come from the state where the free opportunity has been used (used == 1), not the state where it is still available (used == 0).

Why this is wrong: dist[n - 1][0] is the cost of reaching the target while paying for every edge. This corresponds to a path where no edge was dropped, which violates the problem statement. The intended answer always drops one edge, so you must read from dist[n - 1][1].

# WRONG
return dist[n - 1][0]

# CORRECT
return dist[n - 1][1]

Note that even on a single-edge path from 0 to n - 1, that one edge is the maximum and must be dropped — so the cost is 0, which only dist[n - 1][1] captures.

Pitfall 2: Forgetting that "dropping the max edge" is equivalent to "dropping any one edge"

The problem says to exclude the maximum-weight edge, but the code simply allows skipping any one edge for free. New solvers often worry this is incorrect.

Why the equivalence holds: For any fixed path, the choice that minimizes the resulting cost is always to drop the largest edge (dropping a smaller edge would leave a larger one in the sum, yielding a bigger total). Since Dijkstra searches over all paths and all free-drop choices simultaneously, the optimal (path, drop) combination it finds will naturally have the dropped edge being the maximum on that path. Therefore, "drop any one edge" and "drop the max edge" produce the same minimum cost.

Pitfall variant: Trying to track "the current maximum edge weight on the path" as part of the state and subtracting it at the end. This blows up the state space (one state per possible max value) and is unnecessary — the free-edge formulation already handles it cleanly.

Pitfall 3: Not modeling the problem as a layered/expanded state graph

A natural but flawed first attempt is to run plain Dijkstra on the original graph and then "subtract the largest edge" afterward. This fails because:

The largest edge on the shortest path is not necessarily the choice that minimizes total - max. A slightly longer path with a much heavier droppable edge can be cheaper.
You cannot decide which edge to drop greedily during a single-layer traversal.

The expanded state (node, used) is essential: it lets the algorithm carry the "have I dropped an edge yet?" information and explore both branches consistently.

Pitfall 4: Pushing the free-transition with the wrong cost

When using the free opportunity, the next cost must be cost (the edge contributes 0), not cost + w:

# WRONG — still adds the weight
if used == 0:
    next_cost = cost + weight  # bug!
    ...

# CORRECT — the dropped edge costs nothing
if used == 0:
    next_cost = cost
    ...

Adding the weight here silently defeats the entire purpose of the second state.

Pitfall 5: Mishandling graphs with no usable path or trivial `n`

Edge cases to verify:

n == 1: source and target are the same node. dist[0][0] = 0, and since used was never required to be 1 for the start, you should confirm the expected output (typically 0). The early-return if node == n - 1 and used would not trigger for the start since used == 0, so the final return dist[n - 1][1] path matters here.
The problem guarantees the graph is connected, so a path always exists; without that guarantee you would need to handle an inf result.

Ready to land your dream job?

Unlock your dream job with a 5-minute quiz for a personalized study roadmap!

Get My Roadmap

Discover Your Strengths and Weaknesses: Take Our 5-Minute Quiz to Get a Personalized Study Roadmap:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Optimal substructure

Overlapping subproblems

Non-overlapping subproblems

Constant time subproblems

Core Learning

LLD/OOP Interview

Additional Resources

AI Engineering