3123. Find Edges in Shortest Paths Hard

1/**
2 * [3123] Find Edges in Shortest Paths
3 *
4 * You are given an undirected weighted graph of n nodes numbered from 0 to n - 1. The graph consists of m edges represented by a 2D array edges, where edges[i] = [ai, bi, wi] indicates that there is an edge between nodes ai and bi with weight wi.
5 * Consider all the shortest paths from node 0 to node n - 1 in the graph. You need to find a boolean array answer where answer[i] is true if the edge edges[i] is part of at least one shortest path. Otherwise, answer[i] is false.
6 * Return the array answer.
7 * Note that the graph may not be connected.
8 *  
9 * <strong class="example">Example 1:
10 * <img alt="" src="https://assets.leetcode.com/uploads/2024/03/05/graph35drawio-1.png" style="height: 129px; width: 250px;" />
11 * <div class="example-block">
12 * Input: <span class="example-io">n = 6, edges = [[0,1,4],[0,2,1],[1,3,2],[1,4,3],[1,5,1],[2,3,1],[3,5,3],[4,5,2]]</span>
13 * Output: <span class="example-io">[true,true,true,false,true,true,true,false]</span>
14 * Explanation:
15 * The following are all the shortest paths between nodes 0 and 5:
16 * 
17 * 	The path 0 -> 1 -> 5: The sum of weights is 4 + 1 = 5.
18 * 	The path 0 -> 2 -> 3 -> 5: The sum of weights is 1 + 1 + 3 = 5.
19 * 	The path 0 -> 2 -> 3 -> 1 -> 5: The sum of weights is 1 + 1 + 2 + 1 = 5.
20 * </div>
21 * <strong class="example">Example 2:
22 * <img alt="" src="https://assets.leetcode.com/uploads/2024/03/05/graphhhh.png" style="width: 185px; height: 136px;" />
23 * <div class="example-block">
24 * Input: <span class="example-io">n = 4, edges = [[2,0,1],[0,1,1],[0,3,4],[3,2,2]]</span>
25 * Output: <span class="example-io">[true,false,false,true]</span>
26 * Explanation:
27 * There is one shortest path between nodes 0 and 3, which is the path 0 -> 2 -> 3 with the sum of weights 1 + 2 = 3.
28 * </div>
29 *  
30 * Constraints:
31 * 
32 * 	2 <= n <= 5 * 10^4
33 * 	m == edges.length
34 * 	1 <= m <= min(5 * 10^4, n * (n - 1) / 2)
35 * 	0 <= ai, bi < n
36 * 	ai != bi
37 * 	1 <= wi <= 10^5
38 * 	There are no repeated edges.
39 * 
40 */
41pub struct Solution {}
42
43// problem: https://leetcode.com/problems/find-edges-in-shortest-paths/
44// discuss: https://leetcode.com/problems/find-edges-in-shortest-paths/discuss/?currentPage=1&orderBy=most_votes&query=
45
46// submission codes start here
47
48impl Solution {
49    pub fn find_answer(n: i32, edges: Vec<Vec<i32>>) -> Vec<bool> {
50        
51    }
52}
53
54// submission codes end
55
56#[cfg(test)]
57mod tests {
58    use super::*;
59
60    #[test]
61    fn test_3123() {
62    }
63}
64