Leetcode 2203. Minimum Weighted Subgraph With the Required Paths

문제

You are given an integer n denoting the number of nodes of a weighted directed graph. The nodes are numbered from 0 to n - 1.

You are also given a 2D integer array edges where edges[i] = [fromi, toi, weighti] denotes that there exists a directed edge from fromi to toi with weight weighti.

Lastly, you are given three distinct integers src1, src2, and dest denoting three distinct nodes of the graph.

Return the minimum weight of a subgraph of the graph such that it is possible to reach dest from both src1 and src2 via a set of edges of this subgraph. In case such a subgraph does not exist, return -1.

A subgraph is a graph whose vertices and edges are subsets of the original graph. The weight of a subgraph is the sum of weights of its constituent edges.

가중치가 있는 방향 그래프의 노드 개수를 나타내는 정수 n이 주어집니다. 노드의 번호는 0부터 n - 1까지입니다.

또한 2차원 정수 배열 edges가 주어집니다. edges[i] = [from_i, to_i, weight_i]는 from_i 노드에서 to_i 노드로 향하는 가중치 weight_i의 방향 간선이 존재한다는 의미입니다.

마지막으로 서로 다른 세 노드 src1, src2, dest가 주어집니다.

원본 그래프의 일부 간선으로 구성된 부분 그래프 중에서, src1과 src2 모두에서 dest까지 도달할 수 있는 부분 그래프의 최소 가중치를 반환하세요.

이러한 부분 그래프가 존재하지 않는 경우 -1을 반환하세요.

부분 그래프란 원본 그래프의 정점과 간선 중 일부만으로 구성된 그래프입니다.

부분 그래프의 가중치는 해당 부분 그래프에 포함된 모든 간선 가중치의 합입니다.

예시

입력: n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5

출력: 9

설명:

위 그림은 입력으로 주어진 그래프를 나타냅니다.

파란색 간선은 최적의 답을 만드는 부분 그래프 중 하나를 나타냅니다.

[[1,0,3],[0,5,6]]으로 구성된 부분 그래프 역시 최적의 답을 만듭니다.

모든 조건을 만족하면서 가중치의 합이 9보다 작은 부분 그래프를 만드는 것은 불가능합니다.

제한

• $3 \le n \le 10^5$
• $0 \le \text{edges.length} \le 10^5$
• $\text{edges}[i]\text{.length} = 3$
• $0 \le \text{from}_i,\ \text{to}_i,\ \text{src1},\ \text{src2},\ \text{dest} \le n - 1$
• $\text{from}_i \ne \text{to}_i$
• $\text{src1},\ \text{src2},\ \text{dest}$는 서로 다른 값입니다.
• $1 \le \text{weight}_i \le 10^5$

풀이

1. 정방향 그래프와 역방향 그래프를 만든다.
2. src1과 src2에서 시작하는 정방향 그래프에서의 다익스트라를 총 2번 실행
3. dest에서 시작하는 역방향 그래프에서의 다익스트라를 1번 실행
   • 총 3번
4. src1과 src2에서 노드 i로 가는 최단거리와 노드i에서 dest까지 가는 최단거리의 합중 최소값을 찾음

class Solution:
    def minimumWeight(self, n: int, edges: List[List[int]], src1: int, src2: int, dest: int) -> int:
        rev_graph = [[] for _ in range(n)]
        graph = [[] for _ in range(n)]

        for s, e, w in edges:
            rev_graph[e].append((s, w))
            graph[s].append((e, w))

        def dijikstra(g: List[List[int]], s: int) -> List[int]:
            dist = [float('inf')] * n
            heap = [(0, s)]
            dist[s] = 0

            while heap:
                acc, node = heappop(heap)

                if acc > dist[node]:
                    continue

                for dest, weight in g[node]:
                    if dist[dest] <= weight + acc:
                        continue

                    dist[dest] = weight + acc
                    heappush(heap, (weight + acc, dest))

            return dist

        dest_dist = dijikstra(rev_graph, dest)
        src1_dist = dijikstra(graph, src1)
        src2_dist = dijikstra(graph, src2)

        ans = float('inf')

        for i in range(n):
            ans = min(ans, dest_dist[i] + src1_dist[i] + src2_dist[i])

        return ans if ans != float('inf') else -1