Leetcode 3108. Minimum Cost Walk in Weighted Graph

Jimmy   Mar 20, 2025   525 words   ~15 mins
#Array #Bit Manipulation #Union Find #Graph

Table of Contents

題目資訊

題目敘述

有一個無向加權圖，具有 $n$ 個從 $0$ 至 $n - 1$ 標記的頂點。

給定整數 $n$ 和一個陣列 edges，其中 edges[i] = [u_i, v_i, w_i] 表示在頂點 $u_i$ 和頂點 $v_i$ 之間有一條權重為 $w_i$ 的邊。

在圖上的一段行走是頂點與邊的序列。行走始於一個頂點，並在另一個頂點結束，每條邊連接它前後的頂點。需要注意的是，行走可能會多次訪問相同的邊或頂點。

行走從節點 $u$ 開始並在節點 $v$ 結束的成本定義為行走過程中經過邊的權重的位元 AND。換句話說，如果行走過程中遇到的邊權重序列為 $w_0, w_1, w_2, \ldots, w_k$，那麼成本計算為 $w_0$ & $w_1$ & $w_2$ & $\ldots$ & $w_k$，其中 & 表示位元 AND 運算子。

你也將得到一個二維陣列 query，其中 query[i] = [s_i, t_i]。對於每個查詢，你需要找到從頂點 $s_i$ 開始並在頂點 $t_i$ 結束的行走的最小成本。如果不存在這樣的行走，答案為 $-1$。

返回一個陣列 answer，其中 answer[i] 表示查詢 $i$ 的最小行走成本。

範例 1:

輸入: n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]

輸出: [1,-1]

解釋:

範例1圖

要在第一個查詢中達到成本1，我們需要經過以下邊： 0->1 (權重 7), 1->2 (權重 1), 2->1 (權重 1), 1->3 (權重 7)。

在第二個查詢中，節點 3 和 4 之間沒有行走路徑，因此答案是 -1。

範例 2:

輸入: n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]

輸出: [0]

解釋:

範例2圖

要在第一個查詢中達到成本0，我們需要經過以下邊： 1->2 (權重 1), 2->1 (權重 6), 1->2 (權重 1)。

約束條件:

  • $2 \leq n \leq 10^5$
  • $0 \leq \text{edges.length} \leq 10^5$
  • $\text{edges}[i].\text{length} == 3$
  • $0 \leq u_i, v_i \leq n - 1$
  • $u_i \neq v_i$
  • $0 \leq w_i \leq 10^5$
  • $1 \leq \text{query.length} \leq 10^5$
  • $\text{query}[i].\text{length} == 2$
  • $0 \leq s_i, t_i \leq n - 1$
  • $s_i \neq t_i$

直覺

此問題涉及找出無向加權圖中兩個節點之間行走的最小花費。行走的花費由遍歷該路徑的所有邊的權重進行按位AND操作來決定。我們的目標是創建一個有效的演算法來判斷多對節點之間的最小花費。

核心直覺是將圖視為由多個連通組成的連通分量。每個連通分量的邊的權重通過AND操作可獲得唯一的最小權重。通過利用深度優先搜索（DFS），我們可以探索這些組件，對其進行分類，並預先計算每個組件的最小權重。

解法

  1. 圖的表示：

    • 使用鄰接表來表示圖。該鄰接表儲存每條邊及其權重，因為圖是無向的，每條邊需要在兩個方向上都存儲。

  2. 深度優先搜索識別組件：

    • 對圖中的每個節點使用深度優先搜索（DFS）。每個節點屬於一個連通分量。我們為每個組件分配一個索引（即組ID）。
    • 在DFS過程中，保存所有遇到的邊權重的按位AND結果。這個操作可以計算出僅包含在該組件中的任意行走的最小可能花費。

  3. 預處理：

    • 遍歷所有節點。若節點尚未被分配組別，從該節點開始進行DFS，將所有可到達的節點分類至同一組，並使用按位AND計算該組件的最小邊權重。

  4. 處理查詢：

    • 對每個查詢，檢查查詢中兩個節點的組ID。
    • 如果它們屬於不同的組件，則無法完成行走，返回-1。
    • 如果它們在同一個組件中，則返回預先計算的該組件的最小邊權重。

此方法通過最小的預處理將圖中的節點分組成多個組件。它確保每個查詢可以通過檢查節點隸屬於哪個組件在常數時間內得到答案，使得解決方案能夠擴展至較大的輸入規模。

程式碼

C++

class Solution {
public:
    // 輔助函式，用於分配群組索引並確定每個連通組件的最小邊權重
    void set_group(int idx, int group_idx, vector<int>& group, vector<int>& group_val, vector<vector<pair<int, int>>>& edges_ll) {
        if (group[idx] != -1) return; // 節點已分配到某群組
        group[idx] = group_idx; // 將節點分配到當前群組
        for (pair<int, int>& e : edges_ll[idx]) {
            // 更新群組的最小權重
            group_val[group_idx] &= e.second;
            set_group(e.first, group_idx, group, group_val, edges_ll); // 繼續深度優先搜尋
        }
    }

    vector<int> minimumCost(int n, vector<vector<int>>& edges, vector<vector<int>>& query) {
        int group_idx = -1; // 初始化群組索引
        vector<int> group(n, -1); // 每個節點的群組索引，-1 表示未訪問
        vector<int> group_val(n, INT_MAX); // 每個群組的最小邊權重
        vector<vector<pair<int, int>>> edges_ll(n); // 邊的鄰接表
        vector<int> ans; // 儲存查詢結果

        // 建立鄰接表
        for (vector<int>& e : edges) {
            edges_ll[e[0]].push_back({e[1], e[2]});
            edges_ll[e[1]].push_back({e[0], e[2]});
        }

        // 分配連通組件的群組並計算最小邊權重
        for (int i = 0; i < n; i++) {
            if (group[i] != -1) continue; // 節點已訪問
            set_group(i, ++group_idx, group, group_val, edges_ll);
        }

        // 評估每個查詢
        for (vector<int>& q : query) {
            if (group[q[0]] != group[q[1]]) {
                ans.push_back(-1); // 節點位於不同群組中，無路徑存在
            } else {
                ans.push_back(group_val[group[q[0]]]); // 返回群組的最小權重
            }
        }

        return ans; // 返回所有查詢的結果
    }
};

Python

class Solution:
    # 輔助函數來分配群組索引並確定每個連通分量的最小邊權重
    def set_group(self, idx, group_idx, group, group_val, edges_ll):
        if group[idx] != -1:
            return  # 節點已經被分配到一個群組
        group[idx] = group_idx  # 將節點分配到當前群組
        for e in edges_ll[idx]:
            # 更新群組的最小邊權重
            group_val[group_idx] &= e[1]
            self.set_group(e[0], group_idx, group, group_val, edges_ll)  # 繼續進行深度優先搜尋

    def minimumCost(self, n, edges, query):
        group_idx = -1  # 初始化群組索引
        group = [-1] * n  # 每個節點的群組索引，-1表示未訪問
        group_val = [float('inf')] * n  # 每個群組的最小邊權重
        edges_ll = [[] for _ in range(n)]  # 邊的鄰接列表
        ans = []  # 儲存查詢結果

        # 建立鄰接列表
        for e in edges:
            edges_ll[e[0]].append((e[1], e[2]))
            edges_ll[e[1]].append((e[0], e[2]))

        # 給連通分量分配群組並計算最小邊權重
        for i in range(n):
            if group[i] != -1:
                continue  # 節點已被訪問
            self.set_group(i, group_idx + 1, group, group_val, edges_ll)
            group_idx += 1

        # 評估每個查詢
        for q in query:
            if group[q[0]] != group[q[1]]:
                ans.append(-1)  # 節點在不同群組中，無路徑存在
            else:
                ans.append(group_val[group[q[0]]])  # 返回群組的最小權重

        return ans  # 返回所有查詢的結果

複雜度分析

  • 時間複雜度: 給定解決方案的時間複雜度是 $O(n + m)$，其中 $n$ 是圖中頂點的數量，$m$ 是存在於圖中的邊的數量。這一複雜度的產生是因為演算法精確地遍訪每個頂點和每條邊一次。構造鄰接表和透過 set_group 函數分配組別涉及到深度優先搜尋 (DFS)，該搜尋遞迴遍歷每個頂點及其連接的邊各一次。

  • 空間複雜度: 空間複雜度同樣是 $O(n + m)$。這一空間使用來自於圖形的鄰接表表示，這需要存儲 $m$ 個邊，以及存儲每一個 $n$ 個頂點資訊的陣列 group 和 group_val。鄰接表本身使用 $O(m)$ 的空間，而額外的陣列使用 $O(n)$ 的空間。

Disclaimer: All reference materials on this website are sourced from the internet and are intended for learning purposes only. If you believe any content infringes upon your rights, please contact me at csnote.cc@gmail.com, and I will remove the relevant content promptly.


Feedback Welcome: If you notice any errors or areas for improvement in the articles, I warmly welcome your feedback and corrections. Your input will help this blog provide better learning resources. This is an ongoing process of learning and improvement, and your suggestions are valuable to me. You can reach me at csnote.cc@gmail.com.