TheRealSamuel/LeetCodeProblem
0561
1{2 "id": 2803,3 "name": "modify_graph_edge_weights",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/modify-graph-edge-weights/",6 "date": "2023-05-14 00:00:00",7 "task_description": "You are given an **undirected weighted** **connected** graph containing `n` nodes labeled from `0` to `n - 1`, and an integer array `edges` where `edges[i] = [ai, bi, wi]` indicates that there is an edge between nodes `ai` and `bi` with weight `wi`. Some edges have a weight of `-1` (`wi = -1`), while others have a **positive** weight (`wi > 0`). Your task is to modify **all edges** with a weight of `-1` by assigning them **positive integer values **in the range `[1, 2 * 109]` so that the **shortest distance** between the nodes `source` and `destination` becomes equal to an integer `target`. If there are **multiple** **modifications** that make the shortest distance between `source` and `destination` equal to `target`, any of them will be considered correct. Return _an array containing all edges (even unmodified ones) in any order if it is possible to make the shortest distance from _`source`_ to _`destination`_ equal to _`target`_, or an **empty array** if it's impossible._ **Note:** You are not allowed to modify the weights of edges with initial positive weights. **Example 1:** **** ``` **Input:** n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5 **Output:** [[4,1,1],[2,0,1],[0,3,3],[4,3,1]] **Explanation:** The graph above shows a possible modification to the edges, making the distance from 0 to 1 equal to 5. ``` **Example 2:** **** ``` **Input:** n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6 **Output:** [] **Explanation:** The graph above contains the initial edges. It is not possible to make the distance from 0 to 2 equal to 6 by modifying the edge with weight -1. So, an empty array is returned. ``` **Example 3:** **** ``` **Input:** n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6 **Output:** [[1,0,4],[1,2,3],[2,3,5],[0,3,1]] **Explanation:** The graph above shows a modified graph having the shortest distance from 0 to 2 as 6. ``` **Constraints:** `1 <= n <= 100` `1 <= edges.length <= n * (n - 1) / 2` `edges[i].length == 3` `0 <= ai, bi < n` `wi = -1 `or `1 <= wi <= 107` `ai != bi` `0 <= source, destination < n` `source != destination` `1 <= target <= 109` The graph is connected, and there are no self-loops or repeated edges",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "n = 5, edges = [[4,1,-1],[2,0,-1],[0,3,-1],[4,3,-1]], source = 0, destination = 1, target = 5",12 "output": "[[4,1,1],[2,0,1],[0,3,3],[4,3,1]] "13 },14 {15 "label": "Example 2",16 "input": "n = 3, edges = [[0,1,-1],[0,2,5]], source = 0, destination = 2, target = 6",17 "output": "[] "18 },19 {20 "label": "Example 3",21 "input": "n = 4, edges = [[1,0,4],[1,2,3],[2,3,5],[0,3,-1]], source = 0, destination = 2, target = 6",22 "output": "[[1,0,4],[1,2,3],[2,3,5],[0,3,1]] "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 53,29 [30 [31 11,32 0,33 28305097534 ],35 [36 47,37 4,38 30552639 ],40 [41 11,42 40,43 28063449844 ],45 [46 20,47 18,48 313930149 ],50 [51 20,52 47,53 448329654 ],55 [56 27,57 44,58 28504286159 ],60 [61 0,62 19,63 144587064 ],65 [66 10,67 22,68 28694093969 ],70 [71 25,72 40,73 28063450074 ],75 [76 42,77 6,78 904455879 ],80 [81 2,82 14,83 165977284 ],85 [86 13,87 36,88 691730689 ],90 [91 51,92 39,93 28316009994 ],95 [96 12,97 29,98 260257199 ],100 [101 46,102 9,103 4450118104 ],105 [106 3,107 41,108 283422817109 ],110 [111 1,112 32,113 4557467114 ],115 [116 30,117 20,118 8866698119 ],120 [121 48,122 42,123 3101981124 ],125 [126 25,127 12,128 286282999129 ],130 [131 52,132 41,133 280925362134 ],135 [136 26,137 4,138 285566318139 ],140 [141 24,142 22,143 5866705144 ],145 [146 33,147 41,148 284429231149 ],150 [151 23,152 13,153 5345579154 ],155 [156 41,157 17,158 4825543159 ],160 [161 36,162 23,163 8684152164 ],165 [166 50,167 6,168 1965198169 ],170 [171 35,172 36,173 9743593174 ],175 [176 26,177 13,178 279335888179 ],180 [181 46,182 23,183 1487977184 ],185 [186 13,187 28,188 6836205189 ],190 [191 49,192 37,193 282208250194 ],195 [196 6,197 7,198 280630357199 ],200 [201 33,202 20,203 284429231204 ],205 [206 3,207 30,208 283422818209 ],210 [211 27,212 0,213 283050976214 ],215 [216 24,217 36,218 5902085219 ],220 [221 49,222 34,223 282208250224 ],225 [226 20,227 15,228 290094887229 ],230 [231 1,232 44,233 285042859234 ],235 [236 15,237 29,238 290094887239 ],240 [241 23,242 7,243 2695851244 ],245 [246 9,247 0,248 5132332249 ],250 [251 41,252 10,253 280925360254 ],255 [256 7,257 1,258 282984075259 ],260 [261 29,262 19,263 288885567264 ],265 [266 30,267 42,268 286011519269 ],270 [271 27,272 15,273 290094889274 ],275 [276 44,277 32,278 285042859279 ],280 [281 19,282 45,283 1875738284 ],285 [286 39,287 30,288 279996256289 ],290 [291 3,292 6,293 6879685294 ],295 [296 40,297 47,298 285871844299 ],300 [301 36,302 41,303 280925360304 ],305 [306 43,307 46,308 8907056309 ],310 [311 27,312 39,313 282886549314 ],315 [316 52,317 33,318 284429232319 ],320 [321 12,322 23,323 7174837324 ],325 [326 52,327 31,328 6078534329 ],330 [331 24,332 42,333 2044884334 ],335 [336 21,337 20,338 284390916339 ],340 [341 36,342 20,343 284390916344 ],345 [346 12,347 19,348 2002151349 ],350 [351 46,352 25,353 284570377354 ],355 [356 8,357 30,358 279996254359 ],360 [361 1,362 9,363 282984073364 ],365 [366 4,367 40,368 285566318369 ],370 [371 21,372 22,373 286940939374 ],375 [376 35,377 4,378 285566318379 ],380 [381 5,382 22,383 286940941384 ],385 [386 22,387 44,388 286940941389 ],390 [391 18,392 43,393 937064394 ],395 [396 11,397 22,398 286940941399 ],400 [401 34,402 5,403 1179657404 ],405 [406 16,407 4,408 285566320409 ],410 [411 17,412 42,413 286011520414 ],415 [416 24,417 46,418 1384987419 ],420 [421 30,422 12,423 7437917424 ],425 [426 20,427 1,428 1406843429 ],430 [431 45,432 15,433 3722305434 ],435 [436 20,437 4,438 5998509439 ],440 [441 38,442 24,443 283966633444 ],445 [446 40,447 46,448 8510301449 ],450 [451 21,452 30,453 4228180454 ],455 [456 24,457 3,458 4134323459 ],460 [461 7,462 37,463 280630357464 ],465 [466 5,467 39,468 278885451469 ],470 [471 23,472 46,473 7211774474 ],475 [476 26,477 34,478 5726548479 ],480 [481 45,482 30,483 286372583484 ],485 [486 0,487 2,488 283050974489 ],490 [491 25,492 46,493 284570377494 ],495 [496 14,497 25,498 6863397499 ],500 [501 47,502 27,503 285871844504 ],505 [506 14,507 8,508 1509 ],510 [511 49,512 52,513 282208251514 ],515 [516 27,517 17,518 285750906519 ],520 [521 51,522 47,523 2711745524 ],525 [526 4,527 39,528 285566318529 ],530 [531 1,532 34,533 4779673534 ],535 [536 18,537 37,538 9976939539 ],540 [541 28,542 22,543 286940941544 ],545 [546 50,547 21,548 284224432549 ],550 [551 0,552 31,553 1147020554 ],555 [556 6,557 34,558 280065106559 ],560 [561 26,562 49,563 2872363564 ],565 [566 48,567 29,568 227932569 ],570 [571 45,572 1,573 6345482574 ],575 [576 31,577 19,578 284496845579 ],580 [581 5,582 11,583 278885450584 ],585 [586 22,587 48,588 2172559589 ],590 [591 48,592 15,593 981388594 ],595 [596 21,597 29,598 4661133599 ],600 [601 27,602 48,603 6854743604 ],605 [606 52,607 44,608 7677655609 ],610 [611 42,612 5,613 286011519614 ],615 [616 7,617 13,618 280630358619 ],620 [621 27,622 43,623 285153781624 ],625 [626 49,627 22,628 4732690629 ],630 [631 46,632 43,633 5028003634 ],635 [636 24,637 45,638 6673881639 ],640 [641 35,642 27,643 6828793644 ],645 [646 15,647 26,648 290094889649 ],650 [651 22,652 7,653 286940941654 ],655 [656 46,657 33,658 284570375659 ],660 [661 34,662 38,663 283268465664 ],665 [666 36,667 29,668 288885566669 ],670 [671 0,672 17,673 285750905674 ],675 [676 22,677 24,678 286940940679 ],680 [681 45,682 44,683 1329723684 ],685 [686 7,687 26,688 280630359689 ],690 [691 20,692 19,693 105927694 ],695 [696 42,697 47,698 139676699 ],700 [701 32,702 22,703 286940940704 ],705 [706 48,707 5,708 289113500709 ],710 [711 40,712 41,713 4138196714 ],715 [716 5,717 18,718 285264896719 ],720 [721 34,722 32,723 280065106724 ],725 [726 31,727 6,728 7337908729 ],730 [731 1,732 37,733 282984074734 ],735 [736 10,737 49,738 6612030739 ],740 [741 52,742 51,743 283160098744 ],745 [746 0,747 40,748 2530906749 ],750 [751 49,752 15,753 9865029754 ],755 [756 4,757 43,758 412537759 ],760 [761 5,762 29,763 288885568764 ],765 [766 43,767 22,768 286940941769 ],770 [771 50,772 36,773 279917409774 ],775 [776 28,777 12,778 286282997779 ],780 [781 5,782 43,783 7877981784 ],785 [786 44,787 24,788 285042859789 ],790 [791 1,792 32,793 282984074794 ],795 [796 30,797 29,798 288885568799 ],800 [801 7,802 33,803 3798874804 ],805 [806 30,807 3,808 283422818809 ],810 [811 7,812 20,813 284390918814 ],815 [816 28,817 11,818 4894641819 ],820 [821 17,822 12,823 532092824 ],825 [826 5,827 24,828 6174081829 ],830 [831 18,832 42,833 746623834 ],835 [836 40,837 28,838 8958197839 ],840 [841 49,842 1,843 2894281844 ],845 [846 15,847 46,848 5524513849 ],850 [851 19,852 46,853 8005153854 ],855 [856 34,857 31,858 281903954859 ],860 [861 42,862 29,863 288885568864 ],865 [866 33,867 17,868 5516026869 ],870 [871 25,872 27,873 282886550874 ],875 [876 17,877 52,878 285750905879 ],880 [881 38,882 44,883 1774394884 ],885 [886 3,887 20,888 968100889 ],890 [891 5,892 46,893 284570375894 ],895 [896 25,897 16,898 1899 ],900 [901 50,902 40,903 8940759904 ],905 [906 8,907 0,908 283050974909 ],910 [911 45,912 27,913 3486035914 ],915 [916 34,917 51,918 3094991919 ],920 [921 33,922 17,923 1321673924 ],925 [926 17,927 4,928 285750907929 ],930 [931 31,932 26,933 281903956934 ],935 [936 43,937 27,938 4395264939 ],940 [941 40,942 41,943 290864944 ],945 [946 51,947 50,948 3242687949 ]950 ],951 16,952 15,953 290094891954 ],955 "output": [956 [957 11,958 0,959 283050975960 ],961 [962 47,963 4,964 305526965 ],966 [967 11,968 40,969 280634498970 ],971 [972 20,973 18,974 3139301975 ],976 [977 20,978 47,979 4483296980 ],981 [982 27,983 44,984 285042861985 ],986 [987 0,988 19,989 1445870990 ],991 [992 10,993 22,994 286940939995 ],996 [997 25,998 40,999 2806345001000 ],1001 [1002 42,1003 6,1004 90445581005 ],1006 [1007 2,1008 14,1009 16597721010 ],1011 [1012 13,1013 36,1014 69173061015 ],1016 [1017 51,1018 39,1019 2831600991020 ],1021 [1022 12,1023 29,1024 26025711025 ],1026 [1027 46,1028 9,1029 44501181030 ],1031 [1032 3,1033 41,1034 2834228171035 ],1036 [1037 1,1038 32,1039 45574671040 ],1041 [1042 30,1043 20,1044 88666981045 ],1046 [1047 48,1048 42,1049 31019811050 ],1051 [1052 25,1053 12,1054 2862829991055 ],1056 [1057 52,1058 41,1059 2809253621060 ],1061 [1062 26,1063 4,1064 2855663181065 ],1066 [1067 24,1068 22,1069 58667051070 ],1071 [1072 33,1073 41,1074 2844292311075 ],1076 [1077 23,1078 13,1079 53455791080 ],1081 [1082 41,1083 17,1084 48255431085 ],1086 [1087 36,1088 23,1089 86841521090 ],1091 [1092 50,1093 6,1094 19651981095 ],1096 [1097 35,1098 36,1099 97435931100 ],1101 [1102 26,1103 13,1104 2793358881105 ],1106 [1107 46,1108 23,1109 14879771110 ],1111 [1112 13,1113 28,1114 68362051115 ],1116 [1117 49,1118 37,1119 2822082501120 ],1121 [1122 6,1123 7,1124 2806303571125 ],1126 [1127 33,1128 20,1129 2844292311130 ],1131 [1132 3,1133 30,1134 2834228181135 ],1136 [1137 27,1138 0,1139 2830509761140 ],1141 [1142 24,1143 36,1144 59020851145 ],1146 [1147 49,1148 34,1149 2822082501150 ],1151 [1152 20,1153 15,1154 2900948871155 ],1156 [1157 1,1158 44,1159 2850428591160 ],1161 [1162 15,1163 29,1164 2900948871165 ],1166 [1167 23,1168 7,1169 26958511170 ],1171 [1172 9,1173 0,1174 51323321175 ],1176 [1177 41,1178 10,1179 2809253601180 ],1181 [1182 7,1183 1,1184 2829840751185 ],1186 [1187 29,1188 19,1189 2888855671190 ],1191 [1192 30,1193 42,1194 2860115191195 ],1196 [1197 27,1198 15,1199 2900948891200 ],