2492. Minimum Score of a Path Between Two Cities

Medium
Description

有 n 個城市和加權無向邊。路徑的分數是路徑中所有邊的最小權重。求從城市 1 到城市 n 的所有路徑中，最小的分數。路徑可以重複經過節點和邊。

Example:

Input: n = 4, roads = [[1,2,9],[2,3,6],[2,4,5],[1,4,7]] Output: 5

Intuition#

因為可以重複經過邊，答案就是從 1 可達的連通分量中，所有邊的最小權重。

  • 路徑允許重複經過節點和邊，所以不是傳統最短路
  • 只要邊在 1 和 n 的連通分量中，就可以被走到
  • 答案就是這個連通分量中所有邊的最小權重

Approaches#

⭐1: BFS#

  • 概念: 從節點 1 開始 BFS 找出整個連通分量，記錄所有邊的最小權重
  • 時間複雜度: O(V + E)
  • 空間複雜度: O(V + E)
class Solution {
    fun minScore(n: Int, roads: Array<IntArray>): Int {
        val graph = Array(n + 1) { mutableListOf<IntArray>() }
        for ((u, v, w) in roads) {
            graph[u].add(intArrayOf(v, w))
            graph[v].add(intArrayOf(u, w))
        }

        val visited = BooleanArray(n + 1)
        val queue = ArrayDeque<Int>()
        queue.add(1)
        visited[1] = true
        var minWeight = Int.MAX_VALUE

        while (queue.isNotEmpty()) {
            val node = queue.removeFirst()
            for ((next, w) in graph[node]) {
                minWeight = minOf(minWeight, w)
                if (!visited[next]) {
                    visited[next] = true
                    queue.add(next)
                }
            }
        }
        return minWeight
    }
}

2: Union-Find#

  • 概念: 用 Union-Find 找出 1 和 n 所在的連通分量，然後找該分量中所有邊的最小權重
  • 時間複雜度: O(E * α(V))
  • 空間複雜度: O(V)
class Solution {
    private lateinit var parent: IntArray
    private lateinit var rank: IntArray

    fun minScore(n: Int, roads: Array<IntArray>): Int {
        parent = IntArray(n + 1) { it }
        rank = IntArray(n + 1)

        for ((u, v, _) in roads) union(u, v)

        val root = find(1)
        var minWeight = Int.MAX_VALUE
        for ((u, _, w) in roads) {
            if (find(u) == root) {
                minWeight = minOf(minWeight, w)
            }
        }
        return minWeight
    }

    private fun find(x: Int): Int {
        if (parent[x] != x) parent[x] = find(parent[x])
        return parent[x]
    }

    private fun union(x: Int, y: Int) {
        val px = find(x)
        val py = find(y)
        if (px == py) return
        if (rank[px] < rank[py]) parent[px] = py
        else if (rank[px] > rank[py]) parent[py] = px
        else { parent[py] = px; rank[px]++ }
    }
}

🔑 Takeaways#

  • Pattern: 連通分量最小邊 – 允許重複經過時，問題轉化為連通分量內的全域最小值
  • 關鍵技巧: 理解「可重複經過」意味著整個連通分量的所有邊都可被利用，問題大幅簡化