LeetCode 3778 - Minimum Distance Excluding One Maximum Weighted Edge

We are given a connected, weighted, undirected graph with n nodes numbered from 0 to n - 1. Every edge is represented as [u, v, w], meaning there is a bidirectional edge between nodes u and v with positive weight w.

leetcodemedium

LeetCode Problem 3778

Difficulty: 🟡 Medium
Topics: —

Solution

Problem Understanding

We are given a connected, weighted, undirected graph with n nodes numbered from 0 to n - 1. Every edge is represented as [u, v, w], meaning there is a bidirectional edge between nodes u and v with positive weight w.

The objective is to find the minimum cost path from node 0 to node n - 1, but the path cost is defined in an unusual way.

Normally, the cost of a path is the sum of all edge weights. Here, however, we must exclude the edge with the maximum weight from the total. If multiple edges tie for the maximum value, only the first such edge encountered in the path is excluded.

For example, if a path contains edge weights [2, 7, 7, 4], the maximum weight is 7. Since there are two edges with weight 7, only the first 7 is excluded. The final cost becomes:

2 + 7 + 4 = 13

An important observation is that the wording about "the first maximum" may look complicated, but it simplifies significantly. Since exactly one maximum edge is removed from the sum, the problem becomes equivalent to choosing exactly one edge along the path whose cost contribution becomes 0.

Why does this work? Because whenever a larger edge appears later in the path, it retroactively becomes the maximum and effectively replaces the previously excluded edge. In the final accounting, exactly one edge, the first occurrence of the largest weight, contributes 0.

The constraints tell us a lot about the intended solution:

  • n <= 5 * 10^4
  • The graph is connected
  • Edge weights are positive
  • The number of edges is large enough that quadratic or exponential approaches will fail

Since weights are positive, shortest path algorithms such as Dijkstra become immediately relevant. However, a standard shortest path algorithm is insufficient because the path cost depends on a special rule involving one excluded edge.

Some important edge cases stand out immediately:

A path may contain only one edge. In that case, that edge is excluded, so the cost becomes 0.

The optimal path may not be the shortest path by ordinary edge sum. A path with a very large edge can become cheaper if that edge gets excluded.

Multiple maximum-weight edges can exist in a path. Only the first maximum is excluded, but we still pay for later equal-weight edges.

The graph is guaranteed to be connected, so there is always at least one valid path from 0 to n - 1.

Approaches

Brute Force Approach

A naive solution would enumerate every possible path from node 0 to node n - 1, compute the path cost according to the problem rules, and return the minimum.

For each path, we would:

  1. Record all edge weights.
  2. Find the maximum weight.
  3. Exclude the first occurrence of that maximum.
  4. Compute the remaining sum.

This approach is correct because it explicitly checks every valid path and therefore cannot miss the optimal answer.

Unfortunately, it is completely impractical. A graph can contain exponentially many simple paths between two nodes. Even for relatively small graphs, the search space becomes enormous. Since n can reach 50,000, exhaustive path enumeration is impossible.

Key Insight

The key observation is that the problem can be reframed.

Instead of thinking in terms of "exclude the first maximum-weight edge," think of the path as having one free edge.

At any point in the traversal, we are in one of two states:

  • We have not yet used our free exclusion.
  • We have already used it.

Whenever we traverse an edge:

  • We can pay its weight normally.
  • If we have not used the exclusion yet, we may traverse that edge for free.

This converts the problem into a shortest path problem on a graph with two layers of state.

We use Dijkstra's algorithm because:

  • All edge weights are positive.
  • We want a minimum-cost path.
  • We can encode the "free edge used or unused" condition into the state.

Each node effectively becomes two nodes:

  • (u, 0) means we reached node u without using the exclusion.
  • (u, 1) means we reached node u after using the exclusion.

This state expansion allows Dijkstra to correctly explore all valid possibilities efficiently. The optimal answer is the minimum cost to reach (n - 1, 1).

This runs efficiently even for the largest constraints.

Approach Time Complexity Space Complexity Notes
Brute Force Exponential O(n) Enumerates all possible paths
Optimal O((V + E) log V) O(V + E) Modified Dijkstra with two states

Algorithm Walkthrough

Step 1: Build an adjacency list

Convert the edge list into an adjacency list.

Since the graph is undirected, every edge [u, v, w] is added in both directions.

This allows efficient traversal of neighbors during Dijkstra.

Step 2: Create distance tracking with two states

We maintain:

dist[node][used]

Where:

  • used = 0 means we have not used the exclusion yet
  • used = 1 means the exclusion has already been used

Initialize everything to infinity.

Set:

dist[0][0] = 0

because we start at node 0 with no cost and without using the exclusion.

Step 3: Initialize the priority queue

Use a min-heap storing:

(current_cost, node, used)

Initially:

(0, 0, 0)

This means:

  • cost = 0
  • current node = 0
  • exclusion not used

Step 4: Process states using Dijkstra

Pop the state with minimum cost.

If this state is outdated, meaning a better distance already exists, skip it.

Otherwise, examine every neighboring edge.

Step 5: Traverse an edge normally

For an edge (u -> v) with weight w:

We can always pay normally:

new_cost = current_cost + w

If this improves dist[v][used], update it and push the new state into the heap.

Step 6: Use the exclusion if available

If used == 0, we may traverse the edge for free.

That means:

new_cost = current_cost

We transition into state:

used = 1

If this improves the distance, update and push it.

Step 7: Stop when reaching the target

The moment we reach:

(node = n - 1, used = 1)

we can return the answer.

Because Dijkstra guarantees the first extracted state is optimal.

Why it works

The invariant is that dist[u][used] always stores the minimum cost to reach node u under a fixed exclusion state.

Every legal path corresponds to some sequence of transitions between these states. Since Dijkstra explores states in increasing cost order and all edge costs are nonnegative, the first time we reach (n - 1, 1) must be the globally optimal answer.

The two-state representation guarantees we consider every possibility for where the excluded edge appears while never recomputing paths unnecessarily.

Python Solution

from typing import List
import heapq

class Solution:
    def minCostExcludingMax(self, n: int, edges: List[List[int]]) -> int:
        graph = [[] for _ in range(n)]

        for u, v, w in edges:
            graph[u].append((v, w))
            graph[v].append((u, w))

        INF = float("inf")

        # dist[node][used]
        dist = [[INF, INF] for _ in range(n)]
        dist[0][0] = 0

        min_heap = [(0, 0, 0)]  # (cost, node, used)

        while min_heap:
            current_cost, node, used = heapq.heappop(min_heap)

            if current_cost > dist[node][used]:
                continue

            if node == n - 1 and used == 1:
                return current_cost

            for neighbor, weight in graph[node]:
                # Traverse normally
                new_cost = current_cost + weight

                if new_cost < dist[neighbor][used]:
                    dist[neighbor][used] = new_cost
                    heapq.heappush(
                        min_heap,
                        (new_cost, neighbor, used)
                    )

                # Use exclusion if not used yet
                if used == 0:
                    free_cost = current_cost

                    if free_cost < dist[neighbor][1]:
                        dist[neighbor][1] = free_cost
                        heapq.heappush(
                            min_heap,
                            (free_cost, neighbor, 1)
                        )

        return dist[n - 1][1]

The implementation begins by constructing an adjacency list for efficient neighbor access. Since the graph is undirected, every edge is stored in both directions.

The dist array tracks the minimum cost for each node in both exclusion states. This avoids revisiting worse paths and prevents exponential exploration.

The min-heap powers Dijkstra's greedy strategy. At each step, we process the cheapest available state.

For every edge, we attempt two transitions. First, we traverse normally and pay the edge weight. Second, if the exclusion has not yet been used, we try traversing the edge for free and switch to the used = 1 state.

The early return optimization is valid because Dijkstra guarantees the first extracted target state is optimal.

Go Solution

package main

import (
	"container/heap"
	"math"
)

type Edge struct {
	to     int
	weight int64
}

type State struct {
	cost int64
	node int
	used int
}

type MinHeap []State

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].cost < h[j].cost
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(State))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)

	item := old[n-1]
	*h = old[:n-1]

	return item
}

func minCostExcludingMax(n int, edges [][]int) int64 {
	graph := make([][]Edge, n)

	for _, edge := range edges {
		u, v, w := edge[0], edge[1], int64(edge[2])

		graph[u] = append(graph[u], Edge{v, w})
		graph[v] = append(graph[v], Edge{u, w})
	}

	const INF int64 = math.MaxInt64 / 4

	dist := make([][2]int64, n)

	for i := 0; i < n; i++ {
		dist[i][0] = INF
		dist[i][1] = INF
	}

	dist[0][0] = 0

	pq := &MinHeap{}
	heap.Init(pq)

	heap.Push(pq, State{0, 0, 0})

	for pq.Len() > 0 {
		current := heap.Pop(pq).(State)

		cost := current.cost
		node := current.node
		used := current.used

		if cost > dist[node][used] {
			continue
		}

		if node == n-1 && used == 1 {
			return cost
		}

		for _, edge := range graph[node] {
			next := edge.to
			weight := edge.weight

			// Traverse normally
			newCost := cost + weight

			if newCost < dist[next][used] {
				dist[next][used] = newCost
				heap.Push(
					pq,
					State{newCost, next, used},
				)
			}

			// Use exclusion
			if used == 0 {
				freeCost := cost

				if freeCost < dist[next][1] {
					dist[next][1] = freeCost
					heap.Push(
						pq,
						State{freeCost, next, 1},
					)
				}
			}
		}
	}

	return dist[n-1][1]
}

The Go solution mirrors the Python implementation closely but requires an explicit heap implementation using container/heap.

The biggest language-specific difference is integer handling. Since path sums may grow large, int64 is used throughout to avoid overflow.

Go also lacks Python's built-in priority queue, so we define a custom MinHeap implementing the required interface methods.

The dist array uses [2]int64 per node to efficiently store the two states.

Worked Examples

Example 1

Input

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

Graph:

0 --2-- 1 --7-- 2 --7-- 3 --4-- 4

Initial state:

Heap dist
(0,0,0) dist[0][0] = 0

Process (0,0,0):

Action Result
Pay edge 0→1 (2,1,0)
Exclude edge 0→1 (0,1,1)

Process (0,1,1):

Action Result
Pay 1→2 (7) (7,2,1)

Process (2,1,0):

Action Result
Pay 1→2 (9,2,0)
Exclude 1→2 (2,2,1)

Process (2,2,1):

Action Result
Pay 2→3 (7) (9,3,1)

Process (9,3,1):

Action Result
Pay 3→4 (4) (13,4,1)

Reached destination:

answer = 13

The excluded edge is the first 7, exactly matching the problem statement.

Example 2

Input

n = 3
edges = [[0,1,1],[1,2,1],[0,2,50000]]

Initial heap:

(0,0,0)

From node 0:

Transition State
Pay 0→1 (1,1,0)
Exclude 0→1 (0,1,1)
Pay 0→2 (50000,2,0)
Exclude 0→2 (0,2,1)

The priority queue extracts:

(0,2,1)

Since this is the destination with exclusion already used:

answer = 0

The algorithm correctly prefers excluding the direct expensive edge.

Complexity Analysis

Measure Complexity Explanation
Time O((V + E) log V) Dijkstra over twice the number of states
Space O(V + E) Adjacency list, heap, and distance array

Although we conceptually duplicate each node into two states, this only multiplies the graph size by a constant factor. Every edge is relaxed at most twice, once per state, and heap operations dominate the running time.

Because the graph is sparse relative to the constraint sizes, this complexity is efficient enough for n = 50,000.

Test Cases

sol = Solution()

# Example 1
assert sol.minCostExcludingMax(
    5,
    [[0,1,2],[1,2,7],[2,3,7],[3,4,4]]
) == 13  # repeated maximum edge

# Example 2
assert sol.minCostExcludingMax(
    3,
    [[0,1,1],[1,2,1],[0,2,50000]]
) == 0  # single excluded edge gives zero

# Minimum graph size
assert sol.minCostExcludingMax(
    2,
    [[0,1,10]]
) == 0  # only edge excluded

# Prefer excluding expensive edge
assert sol.minCostExcludingMax(
    4,
    [[0,1,1],[1,3,100],[0,2,50],[2,3,50]]
) == 1  # exclude weight 100

# Multiple equal maximums
assert sol.minCostExcludingMax(
    4,
    [[0,1,5],[1,2,5],[2,3,1]]
) == 6  # first 5 excluded

# Dense graph alternative paths
assert sol.minCostExcludingMax(
    4,
    [[0,1,2],[1,3,10],[0,2,6],[2,3,6],[1,2,1]]
) == 2  # best path is not ordinary shortest path

# Long chain
assert sol.minCostExcludingMax(
    5,
    [[0,1,1],[1,2,2],[2,3,3],[3,4,4]]
) == 6  # exclude maximum 4

# Large edge temptation
assert sol.minCostExcludingMax(
    3,
    [[0,1,1],[1,2,1],[0,2,100000]]
) == 0  # direct edge still best
Test Why
Example 1 Verifies repeated maximum handling
Example 2 Verifies single-edge exclusion behavior
n = 2 Smallest possible graph
Expensive edge path Ensures exclusion is used strategically
Equal maximum edges Verifies only one maximum edge is excluded
Dense graph Tests competing routes
Long chain Confirms accumulation logic
Huge direct edge Ensures nontraditional shortest path is chosen

Edge Cases

Single Edge Between Start and Destination

The smallest valid graph contains only two nodes connected by one edge.

Since the path contains exactly one edge, that edge is automatically the maximum and therefore excluded. The answer must be 0.

A naive implementation might incorrectly return the edge weight itself if it forgets to force one exclusion.

Multiple Maximum Edges

A path may contain repeated maximum values such as:

[7, 7, 3]

Only the first 7 is excluded, while later equal values still count.

This can be tricky because it is easy to accidentally remove all maximum edges or the last maximum edge instead. The two-state Dijkstra naturally handles this by allowing exactly one free traversal.

The Optimal Path Is Not the Ordinary Shortest Path

A standard shortest path algorithm minimizing total edge sum can fail badly.

For example:

0 --1-- 1 --100-- 2
 \------50------/

Ordinary shortest path prefers 50.

But excluding 100 makes the longer-looking path cost only 1.

Our stateful Dijkstra correctly evaluates both possibilities because it explicitly models when the exclusion is used.