FPEvalDataset/LeetCodeProblem
0305
1{2 "id": 3348,3 "name": "minimum_cost_walk_in_weighted_graph",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/minimum-cost-walk-in-weighted-graph/",6 "date": "2024-03-31 00:00:00",7 "task_description": "There is an undirected weighted graph with `n` vertices labeled from `0` to `n - 1`. You are given the integer `n` and an array `edges`, where `edges[i] = [ui, vi, wi]` indicates that there is an edge between vertices `ui` and `vi` with a weight of `wi`. A walk on a graph is a sequence of vertices and edges. The walk starts and ends with a vertex, and each edge connects the vertex that comes before it and the vertex that comes after it. It's important to note that a walk may visit the same edge or vertex more than once. The **cost** of a walk starting at node `u` and ending at node `v` is defined as the bitwise `AND` of the weights of the edges traversed during the walk. In other words, if the sequence of edge weights encountered during the walk is `w0, w1, w2, ..., wk`, then the cost is calculated as `w0 & w1 & w2 & ... & wk`, where `&` denotes the bitwise `AND` operator. You are also given a 2D array `query`, where `query[i] = [si, ti]`. For each query, you need to find the minimum cost of the walk starting at vertex `si` and ending at vertex `ti`. If there exists no such walk, the answer is `-1`. Return _the array _`answer`_, where _`answer[i]`_ denotes the **minimum** cost of a walk for query _`i`. **Example 1:** **Input:** n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]] **Output:** [1,-1] **Explanation:** To achieve the cost of 1 in the first query, we need to move on the following edges: `0->1` (weight 7), `1->2` (weight 1), `2->1` (weight 1), `1->3` (weight 7). In the second query, there is no walk between nodes 3 and 4, so the answer is -1. **Example 2:** **Input:** n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]] **Output:** [0] **Explanation:** To achieve the cost of 0 in the first query, we need to move on the following edges: `1->2` (weight 1), `2->1` (weight 6), `1->2` (weight 1). **Constraints:** `2 <= n <= 105` `0 <= edges.length <= 105` `edges[i].length == 3` `0 <= ui, vi <= n - 1` `ui != vi` `0 <= wi <= 105` `1 <= query.length <= 105` `query[i].length == 2` `0 <= si, ti <= n - 1` `si != ti`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "n = 5, edges = [[0,1,7],[1,3,7],[1,2,1]], query = [[0,3],[3,4]]",12 "output": "[1,-1] "13 },14 {15 "label": "Example 2",16 "input": "n = 3, edges = [[0,2,7],[0,1,15],[1,2,6],[1,2,1]], query = [[1,2]]",17 "output": "[0] "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 49,24 [25 [26 41,27 48,28 3762929 ],30 [31 38,32 10,33 7041234 ],35 [36 34,37 17,38 2284239 ],40 [41 20,42 32,43 7477244 ],45 [46 8,47 23,48 111349 ],50 [51 24,52 19,53 2284254 ],55 [56 37,57 44,58 3694959 ],60 [61 41,62 5,63 6797264 ],65 [66 44,67 38,68 3790769 ],70 [71 43,72 31,73 3822274 ],75 [76 28,77 24,78 7810279 ],80 [81 30,82 9,83 596384 ],85 [86 46,87 29,88 1806189 ],90 [91 32,92 35,93 6238194 ],95 [96 9,97 24,98 4567599 ],100 [101 14,102 1,103 85873104 ],105 [106 39,107 37,108 67274109 ],110 [111 0,112 1,113 64181114 ],115 [116 8,117 27,118 21372119 ],120 [121 1,122 40,123 71597124 ],125 [126 28,127 42,128 1479129 ],130 [131 33,132 23,133 62560134 ],135 [136 36,137 45,138 32208139 ],140 [141 32,142 44,143 46364144 ],145 [146 6,147 16,148 17306149 ],150 [151 11,152 43,153 71216154 ],155 [156 23,157 15,158 33934159 ],160 [161 16,162 39,163 88627164 ],165 [166 15,167 27,168 91361169 ],170 [171 32,172 9,173 89543174 ],175 [176 44,177 24,178 78056179 ],180 [181 13,182 20,183 67191184 ],185 [186 15,187 18,188 51669189 ],190 [191 27,192 11,193 39720194 ],195 [196 11,197 24,198 74766199 ],200 [201 7,202 4,203 93324204 ],205 [206 31,207 30,208 17225209 ],210 [211 3,212 11,213 50792214 ],215 [216 34,217 10,218 29505219 ],220 [221 17,222 18,223 19741224 ],225 [226 32,227 38,228 61054229 ],230 [231 39,232 19,233 44199234 ],235 [236 34,237 11,238 5265239 ],240 [241 14,242 2,243 85073244 ],245 [246 17,247 28,248 8942249 ],250 [251 23,252 32,253 26127254 ],255 [256 0,257 25,258 95062259 ],260 [261 40,262 19,263 23114264 ],265 [266 42,267 9,268 68030269 ],270 [271 25,272 21,273 71756274 ],275 [276 24,277 35,278 70505279 ],280 [281 46,282 10,283 87721284 ],285 [286 25,287 15,288 17746289 ],290 [291 7,292 32,293 80185294 ],295 [296 23,297 21,298 95572299 ],300 [301 44,302 28,303 51897304 ],305 [306 5,307 47,308 61254309 ],310 [311 29,312 22,313 87609314 ],315 [316 21,317 44,318 56743319 ],320 [321 38,322 21,323 19782324 ],325 [326 39,327 48,328 66384329 ],330 [331 30,332 43,333 97829334 ],335 [336 27,337 45,338 38437339 ],340 [341 4,342 25,343 16727344 ],345 [346 0,347 31,348 81633349 ],350 [351 43,352 29,353 93590354 ],355 [356 44,357 33,358 24516359 ],360 [361 19,362 0,363 94247364 ],365 [366 22,367 1,368 38646369 ],370 [371 46,372 41,373 89995374 ],375 [376 40,377 16,378 86746379 ],380 [381 27,382 22,383 80835384 ],385 [386 39,387 15,388 50214389 ]390 ],391 [392 [393 12,394 4395 ],396 [397 33,398 28399 ]400 ]401 ],402 "output": [403 -1,404 0405 ]406 },407 {408 "input": [409 35,410 [411 [412 0,413 5,414 57572415 ],416 [417 31,418 30,419 85691420 ],421 [422 29,423 1,424 18805425 ],426 [427 29,428 34,429 14583430 ],431 [432 7,433 23,434 16407435 ],436 [437 2,438 34,439 59404440 ],441 [442 29,443 32,444 28222445 ],446 [447 1,448 19,449 8441450 ],451 [452 7,453 14,454 83575455 ],456 [457 23,458 32,459 43198460 ],461 [462 10,463 26,464 32982465 ],466 [467 0,468 2,469 50600470 ],471 [472 8,473 30,474 87126475 ],476 [477 17,478 18,479 78345480 ],481 [482 20,483 23,484 87989485 ],486 [487 24,488 3,489 85046490 ],491 [492 10,493 12,494 72575495 ],496 [497 3,498 2,499 43326500 ],501 [502 13,503 16,504 74449505 ],506 [507 8,508 18,509 99450510 ],511 [512 11,513 14,514 46262515 ],516 [517 12,518 0,519 19970520 ],521 [522 13,523 4,524 56487525 ],526 [527 3,528 22,529 49620530 ],531 [532 27,533 15,534 28204535 ],536 [537 24,538 16,539 53552540 ],541 [542 2,543 29,544 7224545 ],546 [547 18,548 33,549 22879550 ],551 [552 11,553 28,554 30497555 ],556 [557 29,558 20,559 88739560 ],561 [562 16,563 26,564 88054565 ],566 [567 9,568 3,569 91175570 ],571 [572 1,573 0,574 80024575 ],576 [577 16,578 23,579 93503580 ],581 [582 21,583 10,584 13194585 ],586 [587 22,588 33,589 27324590 ],591 [592 19,593 21,594 11113595 ],596 [597 28,598 17,599 84176600 ],601 [602 33,603 23,604 28508605 ],606 [607 20,608 24,609 19462610 ],611 [612 5,613 16,614 19123615 ],616 [617 29,618 10,619 99723620 ],621 [622 16,623 34,624 18446625 ],626 [627 31,628 2,629 39266630 ]631 ],632 [633 [634 28,635 15636 ],637 [638 23,639 15640 ],641 [642 18,643 7644 ],645 [646 29,647 4648 ],649 [650 22,651 7652 ],653 [654 12,655 1656 ]657 ]658 ],659 "output": [660 -1,661 -1,662 0,663 0,664 0,665 0666 ]667 },668 {669 "input": [670 22,671 [672 [673 0,674 4,675 32851676 ],677 [678 17,679 6,680 53362681 ],682 [683 18,684 9,685 19284686 ],687 [688 0,689 6,690 96597691 ],692 [693 8,694 3,695 60753696 ],697 [698 18,699 21,700 75638701 ],702 [703 19,704 6,705 62581706 ],707 [708 6,709 9,710 60379711 ],712 [713 10,714 6,715 51768716 ],717 [718 2,719 14,720 44947721 ],722 [723 15,724 18,725 48459726 ],727 [728 6,729 12,730 31477731 ],732 [733 15,734 5,735 11030736 ],737 [738 17,739 2,740 75886741 ],742 [743 1,744 20,745 26265746 ],747 [748 10,749 20,750 41554751 ],752 [753 6,754 16,755 37311756 ],757 [758 5,759 10,760 52927761 ],762 [763 17,764 7,765 44965766 ],767 [768 8,769 12,770 51100771 ],772 [773 21,774 9,775 21107776 ],777 [778 14,779 21,780 40088781 ],782 [783 16,784 4,785 198786 ],787 [788 0,789 19,790 8422791 ],792 [793 19,794 8,795 64363796 ],797 [798 6,799 8,800 9962801 ],802 [803 16,804 11,805 16131806 ],807 [808 6,809 13,810 60647811 ],812 [813 10,814 18,815 46647816 ],817 [818 12,819 11,820 86443821 ],822 [823 4,824 6,825 3584826 ],827 [828 16,829 7,830 42442831 ],832 [833 13,834 7,835 4834836 ],837 [838 19,839 15,840 5689841 ],842 [843 7,844 3,845 73902846 ],847 [848 19,849 10,850 89334851 ],852 [853 1,854 0,855 1580856 ],857 [858 19,859 4,860 35001861 ],862 [863 21,864 12,865 30587866 ],867 [868 14,869 17,870 93108871 ]872 ],873 [874 [875 12,876 1877 ]878 ]879 ],880 "output": [881 0882 ]883 },884 {885 "input": [886 32,887 [888 [889 20,890 5,891 1074892 ],893 [894 4,895 15,896 53020897 ],898 [899 4,900 17,901 98815902 ],903 [904 24,905 16,906 61373907 ],908 [909 3,910 22,911 51982912 ],913 [914 8,915 0,916 58547917 ],918 [919 27,920 5,921 83248922 ],923 [924 3,925 8,926 72642927 ],928 [929 8,930 24,931 76975932 ],933 [934 28,935 21,936 86093937 ],938 [939 2,940 21,941 85488942 ],943 [944 1,945 7,946 16314947 ],948 [949 14,950 22,951 37076952 ],953 [954 27,955 13,956 26434957 ],958 [959 23,960 5,961 20646962 ],963 [964 9,965 8,966 1928967 ],968 [969 15,970 9,971 85728972 ]973 ],974 [975 [976 19,977 10978 ],979 [980 20,981 19982 ],983 [984 19,985 16986 ],987 [988 5,989 13990 ],991 [992 22,993 25994 ],995 [996 18,997 8998 ],999 [1000 7,1001 61002 ]1003 ]1004 ],1005 "output": [1006 -1,1007 -1,1008 -1,1009 0,1010 -1,1011 -1,1012 -11013 ]1014 },1015 {1016 "input": [1017 73,1018 [1019 [1020 33,1021 39,1022 372731023 ],1024 [1025 47,1026 36,1027 386721028 ],1029 [1030 53,1031 60,1032 284491033 ],1034 [1035 56,1036 41,1037 425971038 ],1039 [1040 61,1041 9,1042 576061043 ],1044 [1045 6,1046 65,1047 945041048 ],1049 [1050 7,1051 64,1052 789081053 ],1054 [1055 35,1056 17,1057 438101058 ],1059 [1060 62,1061 64,1062 743631063 ],1064 [1065 32,1066 29,1067 478861068 ],1069 [1070 43,1071 3,1072 866201073 ],1074 [1075 25,1076 44,1077 429821078 ],1079 [1080 39,1081 60,1082 678451083 ],1084 [1085 15,1086 18,1087 249681088 ],1089 [1090 32,1091 5,1092 149801093 ],1094 [1095 51,1096 42,1097 667791098 ],1099 [1100 3,1101 4,1102 504011103 ],1104 [1105 67,1106 50,1107 739471108 ],1109 [1110 69,1111 18,1112 155291113 ],1114 [1115 44,1116 47,1117 580501118 ],1119 [1120 66,1121 54,1122 939141123 ],1124 [1125 1,1126 10,1127 257211128 ],1129 [1130 31,1131 66,1132 283401133 ],1134 [1135 8,1136 56,1137 847761138 ],1139 [1140 5,1141 67,1142 283701143 ],1144 [1145 57,1146 13,1147 507281148 ],1149 [1150 41,1151 44,1152 101631153 ],1154 [1155 42,1156 48,1157 485241158 ],1159 [1160 1,1161 59,1162 289211163 ],1164 [1165 66,1166 2,1167 567171168 ],1169 [1170 44,1171 62,1172 947051173 ],1174 [1175 17,1176 50,1177 85321178 ],1179 [1180 68,1181 24,1182 696271183 ],1184 [1185 17,1186 57,1187 598381188 ],1189 [1190 9,1191 71,1192 13191193 ],1194 [1195 1,1196 31,1197 29641198 ],1199 [1200 60,