TheRealSamuel/LeetCodeProblem
0572
1{2 "id": 2321,3 "name": "minimum_weighted_subgraph_with_the_required_paths",4 "difficulty": "Hard",5 "link": "https://leetcode.com/problems/minimum-weighted-subgraph-with-the-required-paths/",6 "date": "1646524800000",7 "task_description": "You are given an integer `n` denoting the number of nodes of a **weighted directed** graph. The nodes are numbered from `0` to `n - 1`. You are also given a 2D integer array `edges` where `edges[i] = [fromi, toi, weighti]` denotes that there exists a **directed** edge from `fromi` to `toi` with weight `weighti`. Lastly, you are given three **distinct** integers `src1`, `src2`, and `dest` denoting three distinct nodes of the graph. Return _the **minimum weight** of a subgraph of the graph such that it is **possible** to reach_ `dest` _from both_ `src1` _and_ `src2` _via a set of edges of this subgraph_. In case such a subgraph does not exist, return `-1`. A **subgraph** is a graph whose vertices and edges are subsets of the original graph. The **weight** of a subgraph is the sum of weights of its constituent edges. **Example 1:** ``` **Input:** n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5 **Output:** 9 **Explanation:** The above figure represents the input graph. The blue edges represent one of the subgraphs that yield the optimal answer. Note that the subgraph [[1,0,3],[0,5,6]] also yields the optimal answer. It is not possible to get a subgraph with less weight satisfying all the constraints. ``` **Example 2:** ``` **Input:** n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2 **Output:** -1 **Explanation:** The above figure represents the input graph. It can be seen that there does not exist any path from node 1 to node 2, hence there are no subgraphs satisfying all the constraints. ``` **Constraints:** `3 <= n <= 105` `0 <= edges.length <= 105` `edges[i].length == 3` `0 <= fromi, toi, src1, src2, dest <= n - 1` `fromi != toi` `src1`, `src2`, and `dest` are pairwise distinct. `1 <= weight[i] <= 105`",8 "public_test_cases": [9 {10 "label": "Example 1",11 "input": "n = 6, edges = [[0,2,2],[0,5,6],[1,0,3],[1,4,5],[2,1,1],[2,3,3],[2,3,4],[3,4,2],[4,5,1]], src1 = 0, src2 = 1, dest = 5",12 "output": "9 "13 },14 {15 "label": "Example 2",16 "input": "n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2",17 "output": "-1 "18 }19 ],20 "private_test_cases": [21 {22 "input": [23 48,24 [25 [26 9,27 32,28 9429 ],30 [31 44,32 30,33 8634 ],35 [36 25,37 23,38 2639 ],40 [41 26,42 42,43 4444 ],45 [46 21,47 46,48 10149 ],50 [51 38,52 43,53 3854 ],55 [56 36,57 16,58 6459 ],60 [61 38,62 45,63 3164 ],65 [66 33,67 42,68 269 ]70 ],71 6,72 47,73 3074 ],75 "output": -176 },77 {78 "input": [79 60,80 [81 [82 53,83 28,84 9685 ],86 [87 6,88 36,89 890 ],91 [92 53,93 31,94 3995 ],96 [97 29,98 19,99 89100 ],101 [102 52,103 1,104 27105 ],106 [107 8,108 59,109 5110 ],111 [112 2,113 43,114 57115 ],116 [117 6,118 2,119 85120 ],121 [122 14,123 1,124 36125 ],126 [127 56,128 28,129 104130 ],131 [132 55,133 15,134 64135 ],136 [137 0,138 12,139 44140 ],141 [142 51,143 29,144 30145 ],146 [147 34,148 47,149 32150 ],151 [152 44,153 4,154 54155 ],156 [157 10,158 34,159 35160 ],161 [162 7,163 46,164 16165 ],166 [167 46,168 18,169 26170 ],171 [172 34,173 17,174 18175 ],176 [177 40,178 10,179 3180 ]181 ],182 15,183 16,184 50185 ],186 "output": -1187 },188 {189 "input": [190 4,191 [192 [193 3,194 1,195 37196 ]197 ],198 3,199 2,200 1201 ],202 "output": -1203 },204 {205 "input": [206 59,207 [208 [209 25,210 55,211 62212 ],213 [214 12,215 26,216 3217 ],218 [219 28,220 19,221 90222 ],223 [224 17,225 52,226 43227 ],228 [229 25,230 33,231 2232 ],233 [234 24,235 47,236 104237 ],238 [239 25,240 41,241 44242 ],243 [244 43,245 25,246 13247 ],248 [249 9,250 12,251 86252 ],253 [254 52,255 36,256 13257 ],258 [259 32,260 45,261 95262 ],263 [264 54,265 52,266 8267 ]268 ],269 49,270 58,271 18272 ],273 "output": -1274 },275 {276 "input": [277 96,278 [279 [280 61,281 76,282 95283 ],284 [285 84,286 19,287 96288 ],289 [290 91,291 21,292 97293 ],294 [295 10,296 73,297 20298 ],299 [300 22,301 71,302 4303 ],304 [305 86,306 9,307 46308 ],309 [310 61,311 54,312 79313 ],314 [315 27,316 62,317 77318 ],319 [320 22,321 24,322 20323 ]324 ],325 20,326 21,327 23328 ],329 "output": -1330 },331 {332 "input": [333 19,334 [335 [336 14,337 16,338 86339 ],340 [341 10,342 12,343 56344 ],345 [346 17,347 7,348 105349 ],350 [351 4,352 15,353 23354 ],355 [356 5,357 4,358 93359 ],360 [361 1,362 12,363 86364 ],365 [366 17,367 16,368 69369 ],370 [371 3,372 4,373 97374 ]375 ],376 13,377 18,378 15379 ],380 "output": -1381 },382 {383 "input": [384 65,385 [386 [387 21,388 22,389 13390 ],391 [392 55,393 0,394 85395 ],396 [397 60,398 20,399 38400 ],401 [402 10,403 7,404 25405 ],406 [407 50,408 34,409 92410 ],411 [412 64,413 27,414 93415 ],416 [417 14,418 15,419 45420 ],421 [422 45,423 15,424 57425 ]426 ],427 51,428 8,429 59430 ],431 "output": -1432 },433 {434 "input": [435 50,436 [437 [438 18,439 22,440 3441 ],442 [443 29,444 38,445 91446 ],447 [448 20,449 46,450 104451 ],452 [453 32,454 11,455 94456 ],457 [458 13,459 23,460 50461 ],462 [463 18,464 41,465 43466 ],467 [468 19,469 31,470 14471 ],472 [473 32,474 49,475 72476 ]477 ],478 31,479 14,480 10481 ],482 "output": -1483 },484 {485 "input": [486 10,487 [488 [489 0,490 5,491 10492 ],493 [494 6,495 8,496 78497 ],498 [499 2,500 7,501 47502 ],503 [504 0,505 9,506 6507 ],508 [509 4,510 5,511 81512 ],513 [514 4,515 7,516 48517 ],518 [519 7,520 9,521 47522 ],523 [524 4,525 5,526 83527 ],528 [529 0,530 8,531 105532 ],533 [534 3,535 4,536 68537 ]538 ],539 4,540 9,541 8542 ],543 "output": -1544 },545 {546 "input": [547 45,548 [549 [550 13,551 26,552 56553 ],554 [555 20,556 8,557 92558 ],559 [560 13,561 34,562 103563 ],564 [565 35,566 34,567 84568 ],569 [570 25,571 2,572 45573 ],574 [575 37,576 38,577 53578 ],579 [580 34,581 21,582 45583 ],584 [585 5,586 40,587 70588 ],589 [590 31,591 23,592 99593 ],594 [595 21,596 43,597 94598 ],599 [600 36,601 22,602 89603 ],604 [605 26,606 9,607 40608 ],609 [610 2,611 42,612 104613 ],614 [615 37,616 17,617 102618 ],619 [620 1,621 21,622 23623 ],624 [625 30,626 6,627 10628 ],629 [630 20,631 22,632 16633 ],634 [635 28,636 7,637 99638 ],639 [640 42,641 36,642 49643 ],644 [645 17,646 27,647 33648 ]649 ],650 25,651 23,652 8653 ],654 "output": -1655 }656 ],657 "haskell_template": "minimumWeight :: Int -> [[Int]] -> Int -> Int -> Int -> Int\nminimumWeight n edges src1 src2 dest ",658 "ocaml_template": "let minimumWeight (n: int) (edges: int list list) (src1: int) (src2: int) (dest: int) : int = ",659 "scala_template": "def minimumWeight(n: Int,edges: List[List[Int]],src1: Int,src2: Int,dest: Int): Int = { \n \n}",660 "java_template": "public static int minimumWeight(int n, List<List<Integer>> edges, int src1, int src2, int dest) {\n\n}",661 "python_template": "class Solution(object):\n def minimumWeight(self, n, edges, src1, src2, dest):\n \"\"\"\n :type n: int\n :type edges: List[List[int]]\n :type src1: int\n :type src2: int\n :type dest: int\n :rtype: int\n \"\"\"\n "662}