Medium

题目描述

给定一个有向加权图，包含 n 个节点，节点标号从 0 到 n-1，以及一个数组 edges，其中 edges[i] = [ui, vi, wi] 表示从节点 ui 到节点 vi 的有向边，权重为 wi。

每个节点 ui 都有一个开关，最多只能使用一次：当你到达 ui 且尚未使用其开关时，可以在其中一条入边 vi → ui 上激活开关，将该边反转为 ui → vi 并立即通过它。

反转只对单次移动有效，使用反转边的代价是 2 * wi。

返回从节点 0 到节点 n-1 的最小总代价。如果不可能到达，返回 -1。

示例 1：

输入：n = 4, edges = [[0,1,3],[3,1,1],[2,3,4],[0,2,2]]
输出：5
解释：
- 使用路径 0 → 1（代价 3）
- 在节点 1 处将原边 3 → 1 反转为 1 → 3 并通过，代价 2 * 1 = 2
- 总代价 3 + 2 = 5

示例 2：

输入：n = 4, edges = [[0,2,1],[2,1,1],[1,3,1],[2,3,3]]
输出：3
解释：不需要反转。路径 0 → 2（代价 1），2 → 1（代价 1），1 → 3（代价 1）
总代价 1 + 1 + 1 = 3

约束条件：

  • 2 <= n <= 5 * 10^4
  • 1 <= edges.length <= 10^5
  • edges[i] = [ui, vi, wi]
  • 0 <= ui, vi <= n - 1
  • 1 <= wi <= 1000

解题思路

这道题可以通过图论中的最短路径算法来解决，关键在于如何处理边的反转机制。

核心思路：

  1. 图的建模：题目允许每个节点最多反转一条入边一次，我们可以将原图扩展为一个新图，其中包含所有原始边和所有可能的反转边。

  2. 状态设计：由于每个节点的开关只能使用一次，我们需要用状态来记录是否已经使用过开关。可以用 (节点, 是否使用过开关) 作为状态。

  3. 建图策略：

    • 保留所有原始边：u → v，权重为 w
    • 为每个原始边添加反向边：v → u，权重为 2*w（但只有在节点u未使用开关时才能使用）

  4. 算法选择：使用 Dijkstra 算法求解最短路径，状态空间为 2n（每个节点有两种状态：使用/未使用开关）。

实现细节：

  • 使用优先队列实现 Dijkstra 算法
  • 状态编码：节点 i 未使用开关为状态 i，使用开关后为状态 i+n
  • 从状态 0 开始，目标是到达状态 n-1 或 2n-1

推荐解法：状态扩展 + Dijkstra 算法，时间复杂度较优且实现清晰。

代码实现

class Solution {
public:
    int minCost(int n, vector<vector<int>>& edges) {
        vector<vector<pair<int, int>>> graph(2 * n);
        
        // 建图：0-n-1表示未使用开关的状态，n-2n-1表示使用过开关的状态
        for (auto& edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            // 原始边：从未使用开关状态到未使用开关状态
            graph[u].push_back({v, w});
            graph[u + n].push_back({v + n, w});
            
            // 反转边：从未使用开关状态到使用开关状态
            graph[v].push_back({u + n, 2 * w});
        }
        
        // Dijkstra算法
        vector<int> dist(2 * n, INT_MAX);
        priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> pq;
        
        dist[0] = 0;
        pq.push({0, 0});
        
        while (!pq.empty()) {
            auto [d, u] = pq.top();
            pq.pop();
            
            if (d > dist[u]) continue;
            
            for (auto& [v, w] : graph[u]) {
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.push({dist[v], v});
                }
            }
        }
        
        int result = min(dist[n - 1], dist[2 * n - 1]);
        return result == INT_MAX ? -1 : result;
    }
};

class Solution:
    def minCost(self, n: int, edges: List[List[int]]) -> int:
        import heapq
        
        # 建图：0-n-1表示未使用开关，n-2n-1表示使用过开关
        graph = [[] for _ in range(2 * n)]
        
        for u, v, w in edges:
            # 原始边
            graph[u].append((v, w))
            graph[u + n].append((v + n, w))
            
            # 反转边：只能从未使用开关状态到使用开关状态
            graph[v].append((u + n, 2 * w))
        
        # Dijkstra算法
        dist = [float('inf')] * (2 * n)
        dist[0] = 0
        pq = [(0, 0)]
        
        while pq:
            d, u = heapq.heappop(pq)
            
            if d > dist[u]:
                continue
                
            for v, w in graph[u]:
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w
                    heapq.heappush(pq, (dist[v], v))
        
        result = min(dist[n - 1], dist[2 * n - 1])
        return result if result != float('inf') else -1

public class Solution {
    public int MinCost(int n, int[][] edges) {
        var graph = new List<(int, int)>[2 * n];
        for (int i = 0; i < 2 * n; i++) {
            graph[i] = new List<(int, int)>();
        }
        
        // 建图
        foreach (var edge in edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            // 原始边
            graph[u].Add((v, w));
            graph[u + n].Add((v + n, w));
            
            // 反转边
            graph[v].Add((u + n, 2 * w));
        }
        
        // Dijkstra算法
        var dist = new int[2 * n];
        Array.Fill(dist, int.MaxValue);
        dist[0] = 0;
        
        var pq = new PriorityQueue<int, int>();
        pq.Enqueue(0, 0);
        
        while (pq.Count > 0) {
            int u = pq.Dequeue();
            
            foreach (var (v, w) in graph[u]) {
                if (dist[u] != int.MaxValue && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.Enqueue(v, dist[v]);
                }
            }
        }
        
        int result = Math.Min(dist[n - 1], dist[2 * n - 1]);
        return result == int.MaxValue ? -1 : result;
    }
}

var minCost = function(n, edges) {
    const graph = Array(n).fill().map(() => []);
    const incomingEdges = Array(n).fill().map(() => []);
    
    for (const [u, v, w] of edges) {
        graph[u].push([v, w]);
        incomingEdges[v].push([u, w]);
    }
    
    const pq = [[0, 0, false]]; // [cost, node, switchUsed]
    const visited = new Set();
    
    while (pq.length > 0) {
        pq.sort((a, b) => a[0] - b[0]);
        const [cost, node, switchUsed] = pq.shift();
        
        if (node === n - 1) {
            return cost;
        }
        
        const stateKey = `${node}-${switchUsed}`;
        if (visited.has(stateKey)) {
            continue;
        }
        visited.add(stateKey);
        
        // Regular outgoing edges
        for (const [nextNode, weight] of graph[node]) {
            pq.push([cost + weight, nextNode, switchUsed]);
        }
        
        // If switch not used, try reversing incoming edges
        if (!switchUsed) {
            for (const [prevNode, weight] of incomingEdges[node]) {
                pq.push([cost + 2 * weight, prevNode, true]);
            }
        }
    }
    
    return -1;
};
在 LeetCode 上运行： 力扣中文版 LeetCode 国际版

复杂度分析

复杂度值
时间复杂度O((V + E) log V)，其中 V = 2n，E 为边数，Dijkstra 算法的标准复杂度
空间复杂度O(V + E) = O(n + edges.length)，用于存储图和距离数组

相关题目