得到要求路径的最小带权子图

/*
 * Problem: Find the minimum weight subgraph in a weighted directed graph such that 
 *          both src1 and src2 can reach dest.
 * Approach:
 * 1. Use Dijkstra's algorithm with Java Streams to find the shortest paths.
 * 2. Calculate the shortest path from src1 to dest, src2 to dest, and dest to any node.
 * 3. Use Streams to iterate through nodes to find the minimum total distance.
 * 4. If no valid path is found, return -1.
 */
import java.util.*;
import java.util.stream.*;

class Solution {
    private static final int INF = Integer.MAX_VALUE;
    public int minimumWeight(int n, int[][] edges, int src1, int src2, int dest) {
        List<int[]>[] graph = IntStream.range(0, n).mapToObj(i -> new ArrayList<int[]>()).toArray(List[]::new);
        List<int[]>[] reverseGraph = IntStream.range(0, n).mapToObj(i -> new ArrayList<int[]>()).toArray(List[]::new);
        Arrays.stream(edges).forEach(edge -> {
            graph[edge[0]].add(new int[]{edge[1], edge[2]});
            reverseGraph[edge[1]].add(new int[]{edge[0], edge[2]});
        });
        long[] distFromSrc1 = dijkstra(graph, n, src1);
        long[] distFromSrc2 = dijkstra(graph, n, src2);
        long[] distToDest = dijkstra(reverseGraph, n, dest);
        return IntStream.range(0, n)
            .filter(i -> distFromSrc1[i] != INF && distFromSrc2[i] != INF && distToDest[i] != INF)
            .mapToLong(i -> distFromSrc1[i] + distFromSrc2[i] + distToDest[i])
            .min().orElse(INF) == INF ? -1 : (int) IntStream.range(0, n)
            .filter(i -> distFromSrc1[i] != INF && distFromSrc2[i] != INF && distToDest[i] != INF)
            .mapToLong(i -> distFromSrc1[i] + distFromSrc2[i] + distToDest[i])
            .min().orElse(INF);
    }

    private long[] dijkstra(List<int[]>[] graph, int n, int start) {
        long[] dist = new long[n];
        Arrays.fill(dist, INF);
        dist[start] = 0;
        PriorityQueue<int[]> pq = new PriorityQueue<>(Comparator.comparingLong(a -> a[1]));
        pq.offer(new int[]{start, 0});
        while (!pq.isEmpty()) {
            int[] curr = pq.poll();
            int u = curr[0];
            long d = curr[1];
            if (d > dist[u]) continue;
            graph[u].forEach(neighbor -> {
                int v = neighbor[0];
                long w = neighbor[1];
                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new int[]{v, (int) dist[v]});
                }
            });
        }
        return dist;
    }
}