解法

思路和算法

根据题目要求，图中有 $n$ 个结点，每个结点最多可以使用一次边反转的开关。对于 $0 \le i < n$ 的每个结点 $i$，使用边反转的开关的效果是将一条终点是结点 $i$ 的边反转成起点是 $i$ 且反转后的边的成本加倍。

由于所有边的成本都是正整数，因此为了将从结点 $0$ 到结点 $n - 1$ 的路径总成本最小化，应确保同一个结点最多访问一次。理由如下：如果一条从结点 $0$ 到结点 $n - 1$ 的路径中存在一个结点访问两次，则将两次访问该结点之间的部分去除之后，该路径仍可以从结点 $0$ 到结点 $n - 1$，且总成本更小。

由于当路径总成本最小时同一个结点最多访问一次，因此边反转的开关的最多可使用一次的限制不需要考虑。对于边数组 $\textit{edges}$ 中的每条边 $[u, v, w]$，等价于如下两条边。

• 从结点 $u$ 出发到达结点 $v$ 的成本为 $w$ 的边。

• 从结点 $v$ 出发到达结点 $u$ 的成本为 $2w$ 的边。

根据边数组 $\textit{edges}$ 中的每条边对应两条边的规则构建有向带权图，然后即可使用最短路算法计算从结点 $0$ 到结点 $n - 1$ 的最小路径总成本。如果不存在从结点 $0$ 到结点 $n - 1$ 的路径，则答案是 $-1$。

由于图中的结点数 $n$ 的最大值是 $5 \times 10^4$，边数组 $\textit{edges}$ 的长度的最大值是 $10^5$，因此这道题适合使用基于小根堆实现的 Dijkstra 算法。

为了方便处理，需要首先将边数组转换成邻接列表的形式，转换后可以使用 $O(1)$ 时间得到一个结点的全部相邻结点。

代码

###Java

class Solution {
    public int minCost(int n, int[][] edges) {
        List<int[]>[] adjacentArr = new List[n];
        for (int i = 0; i < n; i++) {
            adjacentArr[i] = new ArrayList<int[]>();
        }
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adjacentArr[u].add(new int[]{v, w});
            adjacentArr[v].add(new int[]{u, 2 * w});
        }
        int[] distances = new int[n];
        Arrays.fill(distances, Integer.MAX_VALUE);
        distances[0] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((a, b) -> a[1] - b[1]);
        pq.offer(new int[]{0, 0});
        while (!pq.isEmpty()) {
            int[] pair = pq.poll();
            int curr = pair[0], distance = pair[1];
            if (distances[curr] < distance) {
                continue;
            }
            for (int[] adjacent : adjacentArr[curr]) {
                int next = adjacent[0], weight = adjacent[1];
                if (distances[next] > distance + weight) {
                    distances[next] = distance + weight;
                    pq.offer(new int[]{next, distances[next]});
                }
            }
        }
        return distances[n - 1] != Integer.MAX_VALUE ? distances[n - 1] : -1;
    }
}

###C#

public class Solution {
    public int MinCost(int n, int[][] edges) {
        IList<int[]>[] adjacentArr = new IList<int[]>[n];
        for (int i = 0; i < n; i++) {
            adjacentArr[i] = new List<int[]>();
        }
        foreach (int[] edge in edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            adjacentArr[u].Add(new int[]{v, w});
            adjacentArr[v].Add(new int[]{u, 2 * w});
        }
        int[] distances = new int[n];
        Array.Fill(distances, int.MaxValue);
        distances[0] = 0;
        PriorityQueue<int[], int> pq = new PriorityQueue<int[], int>();
        pq.Enqueue(new int[]{0, 0}, 0);
        while (pq.Count > 0) {
            int[] pair = pq.Dequeue();
            int curr = pair[0], distance = pair[1];
            if (distances[curr] < distance) {
                continue;
            }
            foreach (int[] adjacent in adjacentArr[curr]) {
                int next = adjacent[0], weight = adjacent[1];
                if (distances[next] > distance + weight) {
                    distances[next] = distance + weight;
                    pq.Enqueue(new int[]{next, distances[next]}, distances[next]);
                }
            }
        }
        return distances[n - 1] != int.MaxValue ? distances[n - 1] : -1;
    }
}

复杂度分析

• 时间复杂度：$O((n + m) \log n)$，其中 $n$ 是图中的结点数，$m$ 是图中的边数。将边数组转换成邻接列表的时间是 $O(n + m)$，Dijkstra 算法的时间是 $O((n + m) \log n)$，因此时间复杂度是 $O((n + m) \log n)$。

• 空间复杂度：$O(n + m)$，其中 $n$ 是图中的结点数，$m$ 是图中的边数。邻接结点列表的空间是 $O(n + m)$，记录到达每个结点的最小总成本的空间和优先队列的空间是 $O(n)$，因此空间复杂度是 $O(n + m)$。