TheRealSamuel/LeetCodeProblem
0572
1{2 "id": 3389,3 "name": "minimum_time_to_visit_disappearing_nodes",4 "difficulty": "Medium",5 "link": "https://leetcode.com/problems/minimum-time-to-visit-disappearing-nodes/",6 "date": "2024-03-30 00:00:00",7 "task_description": "There is an undirected graph of `n` nodes. You are given a 2D array `edges`, where `edges[i] = [ui, vi, lengthi]` describes an edge between node `ui` and node `vi` with a traversal time of `lengthi` units. Additionally, you are given an array `disappear`, where `disappear[i]` denotes the time when the node `i` disappears from the graph and you won't be able to visit it. **Note** that the graph might be _disconnected_ and might contain _multiple edges_. Return the array `answer`, with `answer[i]` denoting the **minimum** units of time required to reach node `i` from node 0. If node `i` is **unreachable** from node 0 then `answer[i]` is `-1`. **Example 1:** **Input:** n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5] **Output:** [0,-1,4] **Explanation:** We are starting our journey from node 0, and our goal is to find the minimum time required to reach each node before it disappears. For node 0, we don't need any time as it is our starting point. For node 1, we need at least 2 units of time to traverse `edges[0]`. Unfortunately, it disappears at that moment, so we won't be able to visit it. For node 2, we need at least 4 units of time to traverse `edges[2]`. **Example 2:** **Input:** n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5] **Output:** [0,2,3] **Explanation:** We are starting our journey from node 0, and our goal is to find the minimum time required to reach each node before it disappears. For node 0, we don't need any time as it is the starting point. For node 1, we need at least 2 units of time to traverse `edges[0]`. For node 2, we need at least 3 units of time to traverse `edges[0]` and `edges[1]`. **Example 3:** **Input:** n = 2, edges = [[0,1,1]], disappear = [1,1] **Output:** [0,-1] **Explanation:** Exactly when we reach node 1, it disappears. **Constraints:** `1 <= n <= 5 * 104` `0 <= edges.length <= 105` `edges[i] == [ui, vi, lengthi]` `0 <= ui, vi <= n - 1` `1 <= lengthi <= 105` `disappear.length == n` `1 <= disappear[i] <= 105`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,1,5]",12 "output": "[0,-1,4] "13 },14 {15 "label": "Example 2",16 "input": "n = 3, edges = [[0,1,2],[1,2,1],[0,2,4]], disappear = [1,3,5]",17 "output": "[0,2,3] "18 },19 {20 "label": "Example 3",21 "input": "n = 2, edges = [[0,1,1]], disappear = [1,1]",22 "output": "[0,-1] "23 }24 ],25 "private_test_cases": [26 {27 "input": [28 40,29 [30 [31 32,32 34,33 1834334 ],35 [36 8,37 31,38 7272539 ],40 [41 10,42 15,43 7113644 ],45 [46 39,47 26,48 1637749 ],50 [51 37,52 29,53 1698054 ],55 [56 33,57 12,58 6229359 ],60 [61 24,62 30,63 5531664 ],65 [66 23,67 21,68 8410969 ],70 [71 34,72 32,73 7879474 ],75 [76 23,77 15,78 922379 ],80 [81 1,82 13,83 684384 ],85 [86 37,87 31,88 1439489 ],90 [91 32,92 19,93 3961394 ],95 [96 25,97 31,98 8631699 ],100 [101 29,102 3,103 93103104 ]105 ],106 [107 77074,108 6728,109 27928,110 55828,111 60726,112 52810,113 71950,114 66508,115 61485,116 83959,117 37917,118 69397,119 24706,120 45622,121 84064,122 50443,123 86975,124 94863,125 34108,126 41294,127 56557,128 26101,129 9767,130 54711,131 60202,132 55646,133 22838,134 53478,135 81219,136 78625,137 73953,138 49930,139 68469,140 90632,141 45267,142 40127,143 32979,144 40321,145 6570,146 39197147 ]148 ],149 "output": [150 0,151 -1,152 -1,153 -1,154 -1,155 -1,156 -1,157 -1,158 -1,159 -1,160 -1,161 -1,162 -1,163 -1,164 -1,165 -1,166 -1,167 -1,168 -1,169 -1,170 -1,171 -1,172 -1,173 -1,174 -1,175 -1,176 -1,177 -1,178 -1,179 -1,180 -1,181 -1,182 -1,183 -1,184 -1,185 -1,186 -1,187 -1,188 -1,189 -1190 ]191 },192 {193 "input": [194 49,195 [196 [197 5,198 41,199 36037200 ],201 [202 12,203 0,204 97342205 ],206 [207 12,208 9,209 39030210 ],211 [212 34,213 4,214 88801215 ],216 [217 21,218 11,219 4849220 ],221 [222 26,223 13,224 19524225 ],226 [227 11,228 42,229 92534230 ],231 [232 11,233 36,234 66734235 ],236 [237 39,238 8,239 77466240 ],241 [242 28,243 35,244 71358245 ],246 [247 20,248 32,249 8716250 ],251 [252 24,253 14,254 9945255 ],256 [257 6,258 22,259 22193260 ],261 [262 42,263 25,264 216265 ],266 [267 43,268 32,269 63882270 ],271 [272 9,273 5,274 79942275 ],276 [277 40,278 35,279 21347280 ],281 [282 21,283 16,284 34863285 ],286 [287 23,288 48,289 69442290 ],291 [292 12,293 9,294 30565295 ],296 [297 17,298 32,299 87621300 ],301 [302 30,303 24,304 69676305 ],306 [307 0,308 23,309 24683310 ],311 [312 30,313 12,314 6968315 ],316 [317 44,318 29,319 89643320 ],321 [322 15,323 13,324 6126325 ],326 [327 34,328 19,329 37759330 ],331 [332 19,333 38,334 25677335 ],336 [337 30,338 19,339 33700340 ],341 [342 25,343 44,344 16408345 ],346 [347 39,348 46,349 59700350 ],351 [352 26,353 9,354 50205355 ],356 [357 20,358 10,359 31561360 ],361 [362 11,363 30,364 54355365 ],366 [367 6,368 45,369 15814370 ],371 [372 10,373 37,374 76007375 ],376 [377 41,378 27,379 68503380 ],381 [382 24,383 1,384 54713385 ],386 [387 32,388 32,389 57233390 ],391 [392 11,393 29,394 24847395 ],396 [397 28,398 2,399 26753400 ],401 [402 13,403 0,404 84117405 ],406 [407 14,408 14,409 51764410 ],411 [412 35,413 16,414 24723415 ],416 [417 22,418 23,419 84431420 ],421 [422 26,423 28,424 28710425 ],426 [427 26,428 35,429 44422430 ],431 [432 41,433 19,434 87390435 ],436 [437 1,438 14,439 55024440 ],441 [442 48,443 29,444 96874445 ],446 [447 16,448 32,449 56472450 ],451 [452 30,453 2,454 72152455 ],456 [457 14,458 14,459 85884460 ],461 [462 20,463 22,464 41261465 ],466 [467 1,468 13,469 69677470 ],471 [472 43,473 45,474 78793475 ],476 [477 40,478 8,479 16284480 ],481 [482 13,483 31,484 78537485 ],486 [487 34,488 2,489 12856490 ],491 [492 38,493 14,494 35988495 ],496 [497 34,498 6,499 9262500 ],501 [502 8,503 43,504 42841505 ],506 [507 12,508 21,509 62617510 ],511 [512 32,513 33,514 86965515 ],516 [517 38,518 14,519 6892520 ]521 ],522 [523 20687,524 98384,525 38212,526 54509,527 29306,528 28773,529 28352,530 5310,531 87124,532 17079,533 90188,534 6942,535 26433,536 70141,537 74626,538 47882,539 46717,540 94248,541 89139,542 11512,543 93647,544 31680,545 16232,546 29420,547 82239,548 34935,549 67080,550 16404,551 50225,552 29389,553 18635,554 52929,555 83656,556 17306,557 22977,558 84456,559 60955,560 62703,561 97553,562 20035,563 40875,564 58806,565 46383,566 88355,567 56304,568 53725,569 73947,570 63274,571 82742572 ]573 ],574 "output": [575 0,576 -1,577 -1,578 -1,579 -1,580 -1,581 -1,582 -1,583 -1,584 -1,585 -1,586 -1,587 -1,588 -1,589 -1,590 -1,591 -1,592 -1,593 -1,594 -1,595 -1,596 -1,597 -1,598 24683,599 -1,600 -1,601 -1,602 -1,603 -1,604 -1,605 -1,606 -1,607 -1,608 -1,609 -1,610 -1,611 -1,612 -1,613 -1,614 -1,615 -1,616 -1,617 -1,618 -1,619 -1,620 -1,621 -1,622 -1,623 -1624 ]625 },626 {627 "input": [628 37,629 [630 [631 8,632 29,633 91644634 ],635 [636 19,637 9,638 50902639 ],640 [641 36,642 5,643 11003644 ],645 [646 10,647 18,648 55945649 ],650 [651 21,652 2,653 92726654 ],655 [656 11,657 25,658 40278659 ],660 [661 26,662 30,663 23637664 ],665 [666 21,667 18,668 10056669 ],670 [671 11,672 13,673 17941674 ],675 [676 35,677 34,678 12648679 ],680 [681 7,682 8,683 39960684 ],685 [686 18,687 26,688 1059689 ],690 [691 27,692 30,693 44801694 ],695 [696 36,697 18,698 47824699 ],700 [701 16,702 6,703 24522704 ],705 [706 10,707 13,708 36398709 ],710 [711 34,712 31,713 32135714 ],715 [716 18,717 33,718 52524719 ],720 [721 13,722 26,723 60154724 ],725 [726 17,727 22,728 19554729 ],730 [731 23,732 13,733 7790734 ],735 [736 4,737 21,738 69134739 ],740 [741 33,742 32,743 57482744 ],745 [746 18,747 30,748 37828749 ],750 [751 8,752 3,753 70291754 ],755 [756 35,757 6,758 8356759 ],760 [761 25,762 7,763 85958764 ],765 [766 24,767 31,768 63526769 ],770 [771 33,772 33,773 2595774 ],775 [776 21,777 9,778 4714779 ],780 [781 34,782 34,783 58624784 ],785 [786 11,787 33,788 84085789 ],790 [791 4,792 34,793 5132794 ],795 [796 36,797 26,798 11537799 ],800 [801 0,802 10,803 39295804 ],805 [806 16,807 9,808 57315809 ],810 [811 17,812 5,813 48091814 ],815 [816 33,817 19,818 10156819 ],820 [821 30,822 10,823 54528824 ],825 [826 23,827 21,828 22535829 ],830 [831 34,832 29,833 30685834 ],835 [836 13,837 20,838 43435839 ],840 [841 3,842 23,843 22507844 ],845 [846 12,847 31,848 51921849 ],850 [851 36,852 18,853 24964854 ],855 [856 24,857 18,858 74094859 ],860 [861 8,862 31,863 14944864 ],865 [866 23,867 10,868 30978869 ],870 [871 36,872 18,873 17724874 ],875 [876 15,877 2,878 23967879 ],880 [881 17,882 15,883 52014884 ],885 [886 10,887 17,888 39224889 ],890 [891 6,892 17,893 99831894 ],895 [896 13,897 36,898 66778899 ],900 [901 16,902 14,903 44890904 ],905 [906 17,907 25,908 22686909 ],910 [911 12,912 22,913 10026914 ],915 [916 21,917 12,918 46872919 ],920 [921 11,922 28,923 42675924 ],925 [926 9,927 12,928 528929 ],930 [931 20,932 23,933 72435934 ],935 [936 21,937 9,938 55321939 ],940 [941 6,942 32,943 27120944 ],945 [946 31,947 27,948 8173949 ],950 [951 33,952 18,953 98628954 ],955 [956 35,957 3,958 87058959 ],960 [961 7,962 17,963 17661964 ],965 [966 20,967 13,968 67715969 ],970 [971 5,972 22,973 77429974 ],975 [976 23,977 4,978 4390979 ],980 [981 0,982 29,983 65413984 ],985 [986 31,987 21,988 50991989 ],990 [991 14,992 30,993 99511994 ],995 [996 8,997 31,998 96975999 ],1000 [1001 13,1002 29,1003 867191004 ],1005 [1006 9,1007 31,1008 931001009 ],1010 [1011 32,1012 23,1013 228291014 ],1015 [1016 13,1017 7,1018 49761019 ],1020 [1021 10,1022 21,1023 340781024 ],1025 [1026 15,1027 32,1028 162911029 ],1030 [1031 5,1032 0,1033 488091034 ],1035 [1036 16,1037 19,1038 82431039 ],1040 [1041 22,1042 12,1043 510091044 ],1045 [1046 2,1047 19,1048 237691049 ],1050 [1051 7,1052 24,1053 186421054 ],1055 [1056 19,1057 5,1058 315991059 ],1060 [1061 32,1062 1,1063 947731064 ],1065 [1066 24,1067 5,1068 319181069 ],1070 [1071 6,1072 31,1073 542191074 ],1075 [1076 28,1077 18,1078 160911079 ],1080 [1081 9,1082 2,1083 506661084 ],1085 [1086 21,1087 12,1088 206401089 ],1090 [1091 32,1092 20,1093 506111094 ],1095 [1096 32,1097 20,1098 565101099 ],1100 [1101 25,1102 21,1103 418211104 ],1105 [1106 2,1107 8,1108 789001109 ],1110 [1111 26,1112 1,1113 34221114 ],1115 [1116 36,1117 28,1118 882371119 ],1120 [1121 4,1122 16,1123 106231124 ],1125 [1126 20,1127 11,1128 206431129 ]1130 ],1131 [1132 94651,1133 19512,1134 95643,1135 93625,1136 4399,1137 2814,1138 42129,1139 417,1140 56115,1141 90137,1142 97508,1143 36968,1144 59957,1145 81568,1146 36611,1147 15424,1148 37704,1149 32796,1150 77117,1151 71598,1152 4508,1153 86203,1154 42428,1155 92709,1156 57480,1157 51385,1158 39345,1159 30295,1160 87390,1161 55810,1162 27227,1163 23295,1164 33613,1165 60572,1166 87007,1167 42476,1168 618511169 ]1170 ],1171 "output": [1172 0,1173 -1,1174 -1,1175 92780,1176 -1,1177 -1,1178 -1,1179 -1,1180 -1,1181 78087,1182 39295,1183 -1,1184 -1,1185 75693,1186 -1,1187 -1,1188 -1,1189 -1,1190 -1,1191 -1,1192 -1,1193 73373,1194 -1,1195 70273,1196 -1,1197 -1,1198 -1,1199 -1,1200 -1,