2662. Minimum Cost of a Path With Special Roads Medium

1/**
2 * [2662] Minimum Cost of a Path With Special Roads
3 *
4 * You are given an array start where start = [startX, startY] represents your initial position (startX, startY) in a 2D space. You are also given the array target where target = [targetX, targetY] represents your target position (targetX, targetY).
5 * The cost of going from a position (x1, y1) to any other position in the space (x2, y2) is |x2 - x1| + |y2 - y1|.
6 * There are also some special roads. You are given a 2D array specialRoads where specialRoads[i] = [x1i, y1i, x2i, y2i, costi] indicates that the i^th special road goes in one direction from (x1i, y1i) to (x2i, y2i) with a cost equal to costi. You can use each special road any number of times.
7 * Return the minimum cost required to go from (startX, startY) to (targetX, targetY).
8 *  
9 * <strong class="example">Example 1:
10 * <div class="example-block">
11 * Input: <span class="example-io">start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]</span>
12 * Output: <span class="example-io">5</span>
13 * Explanation:
14 * <ol>
15 * 	(1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.
16 * 	(1,2) to (3,3). Use <span class="example-io">specialRoads[0]</span><span class="example-io"> with</span><span class="example-io"> the cost 2.</span>
17 * 	<span class="example-io">(3,3) to (3,4) with a cost of |3 - 3| + |4 - 3| = 1.</span>
18 * 	<span class="example-io">(3,4) to (4,5). Use </span><span class="example-io">specialRoads[1]</span><span class="example-io"> with the cost</span><span class="example-io"> 1.</span>
19 * </ol>
20 * <span class="example-io">So the total cost is 1 + 2 + 1 + 1 = 5.</span>
21 * </div>
22 * <strong class="example">Example 2:
23 * <div class="example-block">
24 * Input: <span class="example-io">start = [3,2], target = [5,7], specialRoads = [[5,7,3,2,1],[3,2,3,4,4],[3,3,5,5,5],[3,4,5,6,6]]</span>
25 * Output: <span class="example-io">7</span>
26 * Explanation:
27 * It is optimal not to use any special edges and go directly from the starting to the ending position with a cost |5 - 3| + |7 - 2| = 7.
28 * Note that the <span class="example-io">specialRoads[0] is directed from (5,7) to (3,2).</span>
29 * </div>
30 * <strong class="example">Example 3:
31 * <div class="example-block">
32 * Input: <span class="example-io">start = [1,1], target = [10,4], specialRoads = [[4,2,1,1,3],[1,2,7,4,4],[10,3,6,1,2],[6,1,1,2,3]]</span>
33 * Output: <span class="example-io">8</span>
34 * Explanation:
35 * <ol>
36 * 	(1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1.
37 * 	(1,2) to (7,4). Use <span class="example-io">specialRoads[1]</span><span class="example-io"> with the cost</span><span class="example-io"> 4.</span>
38 * 	(7,4) to (10,4) with a cost of |10 - 7| + |4 - 4| = 3.
39 * </ol>
40 * </div>
41 *  
42 * Constraints:
43 * 
44 * 	start.length == target.length == 2
45 * 	1 <= startX <= targetX <= 10^5
46 * 	1 <= startY <= targetY <= 10^5
47 * 	1 <= specialRoads.length <= 200
48 * 	specialRoads[i].length == 5
49 * 	startX <= x1i, x2i <= targetX
50 * 	startY <= y1i, y2i <= targetY
51 * 	1 <= costi <= 10^5
52 * 
53 */
54pub struct Solution {}
55
56// problem: https://leetcode.com/problems/minimum-cost-of-a-path-with-special-roads/
57// discuss: https://leetcode.com/problems/minimum-cost-of-a-path-with-special-roads/discuss/?currentPage=1&orderBy=most_votes&query=
58
59// submission codes start here
60
61impl Solution {
62    pub fn minimum_cost(start: Vec<i32>, target: Vec<i32>, special_roads: Vec<Vec<i32>>) -> i32 {
63        0
64    }
65}
66
67// submission codes end
68
69#[cfg(test)]
70mod tests {
71    use super::*;
72
73    #[test]
74    fn test_2662() {
75    }
76}
77