2642. Design Graph With Shortest Path Calculator Hard

1/**
2 * [2642] Design Graph With Shortest Path Calculator
3 *
4 * There is a directed weighted graph that consists of n nodes numbered from 0 to n - 1. The edges of the graph are initially represented by the given array edges where edges[i] = [fromi, toi, edgeCosti] meaning that there is an edge from fromi to toi with the cost edgeCosti.
5 * Implement the Graph class:
6 * 
7 * 	Graph(int n, int[][] edges) initializes the object with n nodes and the given edges.
8 * 	addEdge(int[] edge) adds an edge to the list of edges where edge = [from, to, edgeCost]. It is guaranteed that there is no edge between the two nodes before adding this one.
9 * 	int shortestPath(int node1, int node2) returns the minimum cost of a path from node1 to node2. If no path exists, return -1. The cost of a path is the sum of the costs of the edges in the path.
10 * 
11 *  
12 * <strong class="example">Example 1:
13 * <img alt="" src="https://assets.leetcode.com/uploads/2023/01/11/graph3drawio-2.png" style="width: 621px; height: 191px;" />
14 * Input
15 * ["Graph", "shortestPath", "shortestPath", "addEdge", "shortestPath"]
16 * [[4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]], [3, 2], [0, 3], [[1, 3, 4]], [0, 3]]
17 * Output
18 * [null, 6, -1, null, 6]
19 * Explanation
20 * Graph g = new Graph(4, [[0, 2, 5], [0, 1, 2], [1, 2, 1], [3, 0, 3]]);
21 * g.shortestPath(3, 2); // return 6. The shortest path from 3 to 2 in the first diagram above is 3 -> 0 -> 1 -> 2 with a total cost of 3 + 2 + 1 = 6.
22 * g.shortestPath(0, 3); // return -1. There is no path from 0 to 3.
23 * g.addEdge([1, 3, 4]); // We add an edge from node 1 to node 3, and we get the second diagram above.
24 * g.shortestPath(0, 3); // return 6. The shortest path from 0 to 3 now is 0 -> 1 -> 3 with a total cost of 2 + 4 = 6.
25 * 
26 *  
27 * Constraints:
28 * 
29 * 	1 <= n <= 100
30 * 	0 <= edges.length <= n * (n - 1)
31 * 	edges[i].length == edge.length == 3
32 * 	0 <= fromi, toi, from, to, node1, node2 <= n - 1
33 * 	1 <= edgeCosti, edgeCost <= 10^6
34 * 	There are no repeated edges and no self-loops in the graph at any point.
35 * 	At most 100 calls will be made for addEdge.
36 * 	At most 100 calls will be made for shortestPath.
37 * 
38 */
39pub struct Solution {}
40
41// problem: https://leetcode.com/problems/design-graph-with-shortest-path-calculator/
42// discuss: https://leetcode.com/problems/design-graph-with-shortest-path-calculator/discuss/?currentPage=1&orderBy=most_votes&query=
43
44// submission codes start here
45
46struct Graph {
47        false
48    }
49
50
51/** 
52 * `&self` means the method takes an immutable reference.
53 * If you need a mutable reference, change it to `&mut self` instead.
54 */
55impl Graph {
56
57    fn new(n: i32, edges: Vec<Vec<i32>>) -> Self {
58        
59    }
60    
61    fn add_edge(&self, edge: Vec<i32>) {
62        
63    }
64    
65    fn shortest_path(&self, node1: i32, node2: i32) -> i32 {
66        
67    }
68}
69
70/**
71 * Your Graph object will be instantiated and called as such:
72 * let obj = Graph::new(n, edges);
73 * obj.add_edge(edge);
74 * let ret_2: i32 = obj.shortest_path(node1, node2);
75 */
76
77// submission codes end
78
79#[cfg(test)]
80mod tests {
81    use super::*;
82
83    #[test]
84    fn test_2642() {
85    }
86}
87