TheRealSamuel/LeetCodeProblem
0572
1{2 "id": 2686,3 "name": "minimum_cost_of_a_path_with_special_roads",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/minimum-cost-of-a-path-with-special-roads/",6 "date": "1682208000000",7 "task_description": "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)`. The **cost** of going from a position `(x1, y1)` to any other position in the space `(x2, y2)` is `|x2 - x1| + |y2 - y1|`. There are also some **special roads**. You are given a 2D array `specialRoads` where `specialRoads[i] = [x1i, y1i, x2i, y2i, costi]` indicates that the `ith` 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. Return the **minimum** cost required to go from `(startX, startY)` to `(targetX, targetY)`. **Example 1:** **Input:** start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]] **Output:** 5 **Explanation:** (1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1. (1,2) to (3,3). Use `specialRoads[0]` with the cost 2. (3,3) to (3,4) with a cost of |3 - 3| + |4 - 3| = 1. (3,4) to (4,5). Use `specialRoads[1]` with the cost 1. So the total cost is 1 + 2 + 1 + 1 = 5. **Example 2:** **Input:** 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]] **Output:** 7 **Explanation:** 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. Note that the `specialRoads[0]` is directed from (5,7) to (3,2). **Example 3:** **Input:** 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]] **Output:** 8 **Explanation:** (1,1) to (1,2) with a cost of |1 - 1| + |2 - 1| = 1. (1,2) to (7,4). Use `specialRoads[1]` with the cost 4. (7,4) to (10,4) with a cost of |10 - 7| + |4 - 4| = 3. **Constraints:** `start.length == target.length == 2` `1 <= startX <= targetX <= 105` `1 <= startY <= targetY <= 105` `1 <= specialRoads.length <= 200` `specialRoads[i].length == 5` `startX <= x1i, x2i <= targetX` `startY <= y1i, y2i <= targetY` `1 <= costi <= 105`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "start = [1,1], target = [4,5], specialRoads = [[1,2,3,3,2],[3,4,4,5,1]]",12 "output": "5 "13 },14 {15 "label": "Example 2",16 "input": "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]]",17 "output": "7 "18 },19 {20 "label": "Example 3",21 "input": "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]]",22 "output": "8 "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 [29 80,30 5331 ],32 [33 94,34 5635 ],36 [37 [38 84,39 56,40 93,41 55,42 5243 ],44 [45 88,46 54,47 84,48 54,49 3850 ],51 [52 90,53 53,54 92,55 54,56 2857 ],58 [59 94,60 54,61 83,62 56,63 1364 ],65 [66 88,67 53,68 94,69 53,70 8171 ],72 [73 93,74 54,75 92,76 53,77 5278 ],79 [80 94,81 55,82 85,83 53,84 1585 ],86 [87 93,88 53,89 83,90 56,91 10092 ],93 [94 81,95 54,96 83,97 56,98 5799 ],100 [101 91,102 54,103 83,104 53,105 50106 ],107 [108 84,109 54,110 82,111 56,112 11113 ],114 [115 82,116 56,117 81,118 56,119 49120 ],121 [122 80,123 55,124 88,125 56,126 50127 ],128 [129 81,130 56,131 92,132 53,133 26134 ],135 [136 92,137 55,138 92,139 55,140 44141 ],142 [143 85,144 53,145 88,146 56,147 95148 ],149 [150 84,151 55,152 89,153 56,154 97155 ],156 [157 83,158 55,159 87,160 54,161 14162 ],163 [164 89,165 53,166 89,167 56,168 13169 ],170 [171 90,172 55,173 83,174 56,175 82176 ],177 [178 88,179 55,180 83,181 54,182 10183 ],184 [185 88,186 56,187 84,188 53,189 22190 ],191 [192 84,193 55,194 80,195 53,196 61197 ],198 [199 80,200 53,201 82,202 54,203 12204 ],205 [206 93,207 56,208 84,209 56,210 33211 ],212 [213 91,214 54,215 86,216 54,217 31218 ],219 [220 93,221 55,222 87,223 55,224 63225 ],226 [227 82,228 56,229 84,230 54,231 8232 ],233 [234 85,235 53,236 82,237 53,238 24239 ],240 [241 83,242 56,243 82,244 55,245 44246 ],247 [248 86,249 54,250 93,251 53,252 5253 ],254 [255 91,256 53,257 84,258 55,259 58260 ],261 [262 87,263 55,264 80,265 55,266 86267 ],268 [269 83,270 53,271 86,272 53,273 41274 ],275 [276 93,277 55,278 92,279 54,280 14281 ],282 [283 90,284 53,285 87,286 55,287 101288 ],289 [290 83,291 54,292 94,293 55,294 47295 ],296 [297 88,298 54,299 88,300 55,301 65302 ],303 [304 85,305 56,306 84,307 56,308 67309 ],310 [311 87,312 55,313 88,314 54,315 69316 ],317 [318 90,319 54,320 92,321 53,322 100323 ],324 [325 89,326 55,327 86,328 55,329 24330 ],331 [332 81,333 55,334 88,335 56,336 35337 ],338 [339 80,340 55,341 83,342 55,343 102344 ],345 [346 81,347 55,348 81,349 53,350 67351 ],352 [353 85,354 54,355 85,356 53,357 40358 ],359 [360 81,361 56,362 85,363 54,364 17365 ],366 [367 89,368 53,369 92,370 53,371 62372 ],373 [374 83,375 54,376 80,377 53,378 9379 ],380 [381 89,382 55,383 90,384 56,385 22386 ],387 [388 87,389 56,390 90,391 55,392 96393 ],394 [395 80,396 55,397 94,398 55,399 10400 ],401 [402 86,403 53,404 86,405 53,406 23407 ],408 [409 87,410 55,411 92,412 53,413 91414 ],415 [416 89,417 56,418 84,419 54,420 64421 ],422 [423 88,424 55,425 83,426 54,427 75428 ],429 [430 88,431 55,432 82,433 54,434 104435 ],436 [437 85,438 54,439 94,440 54,441 98442 ],443 [444 84,445 54,446 90,447 55,448 92449 ],450 [451 83,452 54,453 93,454 55,455 26456 ],457 [458 80,459 55,460 86,461 55,462 95463 ],464 [465 83,466 56,467 85,468 56,469 63470 ],471 [472 81,473 55,474 91,475 54,476 60477 ],478 [479 93,480 55,481 87,482 56,483 9484 ],485 [486 84,487 54,488 87,489 56,490 62491 ],492 [493 84,494 53,495 84,496 53,497 94498 ],499 [500 90,501 56,502 88,503 54,504 75505 ],506 [507 91,508 55,509 91,510 56,511 23512 ],513 [514 83,515 55,516 91,517 53,518 102519 ],520 [521 89,522 56,523 92,524 56,525 99526 ],527 [528 94,529 53,530 85,531 53,532 68533 ],534 [535 91,536 55,537 81,538 53,539 31540 ],541 [542 88,543 55,544 86,545 55,546 76547 ],548 [549 89,550 55,551 80,552 53,553 48554 ],555 [556 82,557 53,558 89,559 56,560 85561 ],562 [563 83,564 53,565 84,566 53,567 75568 ],569 [570 90,571 54,572 84,573 53,574 95575 ]576 ]577 ],578 "output": 13579 },580 {581 "input": [582 [583 89,584 79585 ],586 [587 102,588 87589 ],590 [591 [592 97,593 86,594 92,595 83,596 69597 ],598 [599 94,600 80,601 95,602 82,603 80604 ],605 [606 91,607 83,608 94,609 82,610 22611 ],612 [613 98,614 80,615 95,616 79,617 34618 ],619 [620 92,621 87,622 90,623 79,624 91625 ],626 [627 102,628 83,629 99,630 86,631 14632 ],633 [634 101,635 81,636 100,637 80,638 24639 ],640 [641 90,642 79,643 99,644 87,645 10646 ],647 [648 90,649 81,650 89,651 82,652 23653 ],654 [655 98,656 83,657 97,658 80,659 81660 ],661 [662 90,663 86,664 101,665 79,666 19667 ],668 [669 95,670 84,671 93,672 81,673 100674 ],675 [676 93,677 79,678 93,679 87,680 85681 ],682 [683 100,684 83,685 100,686 80,687 53688 ],689 [690 97,691 82,692 101,693 84,694 31695 ],696 [697 93,698 82,699 93,700 83,701 71702 ],703 [704 100,705 87,706 89,707 86,708 99709 ],710 [711 102,712 86,713 101,714 86,715 1716 ],717 [718 95,719 87,720 98,721 82,722 13723 ],724 [725 101,726 84,727 101,728 82,729 65730 ],731 [732 92,733 84,734 101,735 84,736 98737 ],738 [739 89,740 81,741 102,742 83,743 49744 ],745 [746 89,747 86,748 94,749 84,750 90751 ],752 [753 93,754 82,755 97,756 81,757 100758 ],759 [760 97,761 80,762 92,763 85,764 49765 ],766 [767 101,768 83,769 94,770 82,771 91772 ],773 [774 93,775 83,776 102,777 81,778 99779 ],780 [781 96,782 85,783 97,784 85,785 7786 ],787 [788 90,789 87,790 92,791 85,792 62793 ],794 [795 95,796 86,797 100,798 87,799 65800 ],801 [802 101,803 84,804 100,805 80,806 17807 ],808 [809 89,810 84,811 102,812 81,813 60814 ],815 [816 93,817 85,818 98,819 85,820 1821 ],822 [823 101,824 82,825 92,826 80,827 103828 ],829 [830 96,831 81,832 91,833 80,834 97835 ],836 [837 89,838 80,839 96,840 86,841 7842 ],843 [844 92,845 82,846 91,847 87,848 103849 ],850 [851 91,852 81,853 96,854 84,855 71856 ],857 [858 90,859 84,860 94,861 86,862 40863 ],864 [865 97,866 79,867 94,868 80,869 102870 ],871 [872 98,873 86,874 96,875 79,876 5877 ],878 [879 95,880 82,881 101,882 81,883 39884 ],885 [886 94,887 80,888 95,889 86,890 98891 ],892 [893 91,894 87,895 91,896 82,897 17898 ],899 [900 96,901 85,902 101,903 83,904 48905 ],906 [907 92,908 84,909 90,910 81,911 84912 ],913 [914 98,915 84,916 89,917 86,918 79919 ],920 [921 102,922 86,923 101,924 87,925 105926 ],927 [928 98,929 87,930 91,931 81,932 86933 ],934 [935 102,936 86,937 92,938 79,939 100940 ],941 [942 102,943 86,944 98,945 85,946 33947 ],948 [949 95,950 86,951 94,952 81,953 99954 ],955 [956 97,957 85,958 90,959 82,960 12961 ],962 [963 101,964 79,965 97,966 85,967 33968 ],969 [970 99,971 82,972 99,973 85,974 67975 ],976 [977 99,978 86,979 100,980 80,981 57982 ],983 [984 101,985 81,986 96,987 79,988 89989 ],990 [991 89,992 83,993 91,994 87,995 19996 ],997 [998 90,999 86,1000 97,1001 82,1002 441003 ],1004 [1005 92,1006 82,1007 91,1008 79,1009 821010 ],1011 [1012 96,1013 84,1014 97,1015 82,1016 201017 ],1018 [1019 95,1020 79,1021 94,1022 81,1023 861024 ],1025 [1026 91,1027 84,1028 102,1029 84,1030 311031 ],1032 [1033 91,1034 87,1035 100,1036 84,1037 891038 ],1039 [1040 99,1041 82,1042 99,1043 81,1044 891045 ],1046 [1047 98,1048 83,1049 98,1050 84,1051 731052 ],1053 [1054 97,1055 80,1056 94,1057 80,1058 1001059 ],1060 [1061 89,1062 83,1063 100,1064 87,1065 361066 ],1067 [1068 98,1069 86,1070 96,1071 86,1072 821073 ],1074 [1075 94,1076 79,1077 98,1078 86,1079 681080 ],1081 [1082 91,1083 86,1084 93,1085 84,1086 511087 ],1088 [1089 90,1090 80,1091 96,1092 85,1093 21094 ],1095 [1096 102,1097 82,1098 100,1099 86,1100 961101 ],1102 [1103 89,1104 84,1105 92,1106 81,1107 281108 ],1109 [1110 93,1111 81,1112 92,1113 87,1114 441115 ],1116 [1117 89,1118 82,1119 102,1120 83,1121 91122 ],1123 [1124 101,1125 84,1126 90,1127 87,1128 961129 ],1130 [1131 101,1132 86,1133 95,1134 80,1135 921136 ],1137 [1138 101,1139 87,1140 96,1141 83,1142 31143 ],1144 [1145 102,1146 79,1147 94,1148 82,1149 311150 ],1151 [1152 93,1153 86,1154 91,1155 85,1156 461157 ],1158 [1159 101,1160 81,1161 100,1162 87,1163 441164 ],1165 [1166 92,1167 86,1168 90,1169 87,1170 31171 ],1172 [1173 94,1174 83,1175 89,1176 82,1177 551178 ],1179 [1180 98,1181 84,1182 96,1183 80,1184 561185 ],1186 [1187 90,1188 83,1189 100,1190 82,1191 251192 ],1193 [1194 92,1195 85,1196 97,1197 85,1198 681199 ],1200 [