minimum-weighted-subgraph-with-the-required-paths

java

python

python3

mysql

mssql

oraclesql

csharp

javascript

typescript

bash

swift

kotlin

dart

golang

ruby

scala

rust

racket

erlang

elixir

pythondata

postgresql

cangjie

Algorithms

You are given an integer <code>n</code> denoting the number of nodes of a weighted directed graph. The nodes are numbered from <code>0</code> to <code>n - 1</code>.

You are also given a 2D integer array <code>edges</code> where <code>edges[i] = [fromi, toi, weighti]</code> denotes that there exists a directed edge from <code>fromi</code> to <code>toi</code> with weight <code>weighti</code>.

Lastly, you are given three distinct integers <code>src1</code>, <code>src2</code>, and <code>dest</code> denoting three distinct nodes of the graph.

Return the minimum weight of a subgraph of the graph such that it is possible to reach <code>dest</code> from both <code>src1</code> and <code>src2</code> via a set of edges of this subgraph. In case such a subgraph does not exist, return <code>-1</code>.

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.

&nbsp;
Example 1:
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example1drawio.png" style="width: 263px; height: 250px;" />
<pre>
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.
</pre>

Example 2:
<img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example2-1drawio.png" style="width: 350px; height: 51px;" />
<pre>
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.
</pre>

&nbsp;
Constraints:

<ul>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= edges.length &lt;= 105</code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= fromi, toi, src1, src2, dest &lt;= n - 1</code></li>
	<li><code>fromi != toi</code></li>
	<li><code>src1</code>, <code>src2</code>, and <code>dest</code> are pairwise distinct.</li>
	<li><code>1 &lt;= weight[i] &lt;= 105</code></li>
</ul>

minimumWeight

Minimum Weighted Subgraph With the Required Paths

Minimum Cost to Make at Least One Valid Path in a Grid

minimum-cost-to-make-at-least-one-valid-path-in-a-grid

使网格图至少有一条有效路径的最小代价

Escape the Spreading Fire

escape-the-spreading-fire

逃离火灾

Disconnect Path in a Binary Matrix by at Most One Flip

disconnect-path-in-a-binary-matrix-by-at-most-one-flip

二进制矩阵中翻转最多一次使路径不连通

Graph

Shortest Path

给你一个整数&nbsp;<code>n</code>&nbsp;，它表示一个 带权有向 图的节点数，节点编号为&nbsp;<code>0</code> 到&nbsp;<code>n - 1</code>&nbsp;。

同时给你一个二维整数数组&nbsp;<code>edges</code>&nbsp;，其中&nbsp;<code>edges[i] = [fromi, toi, weighti]</code>&nbsp;，表示从&nbsp;<code>fromi</code>&nbsp;到&nbsp;<code>toi</code>&nbsp;有一条边权为&nbsp;<code>weighti</code>&nbsp;的 有向 边。

最后，给你三个 互不相同&nbsp;的整数&nbsp;<code>src1</code>&nbsp;，<code>src2</code>&nbsp;和&nbsp;<code>dest</code>&nbsp;，表示图中三个不同的点。

请你从图中选出一个 边权和最小&nbsp;的子图，使得从 <code>src1</code>&nbsp;和 <code>src2</code>&nbsp;出发，在这个子图中，都 可以&nbsp;到达 <code>dest</code>&nbsp;。如果这样的子图不存在，请返回 <code>-1</code>&nbsp;。

子图&nbsp;中的点和边都应该属于原图的一部分。子图的边权和定义为它所包含的所有边的权值之和。

&nbsp;

示例 1：

<img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example1drawio.png" style="width: 263px; height: 250px;" />

<pre>
输入：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
输出：9
解释：
上图为输入的图。
蓝色边为最优子图之一。
注意，子图 [[1,0,3],[0,5,6]] 也能得到最优解，但无法在满足所有限制的前提下，得到更优解。
</pre>

示例 2：

<img alt="" src="https://assets.leetcode.com/uploads/2022/02/17/example2-1drawio.png" style="width: 350px; height: 51px;" />

<pre>
输入：n = 3, edges = [[0,1,1],[2,1,1]], src1 = 0, src2 = 1, dest = 2
输出：-1
解释：
上图为输入的图。
可以看到，不存在从节点 1 到节点 2 的路径，所以不存在任何子图满足所有限制。
</pre>

&nbsp;

提示：

<ul>
	<li><code>3 &lt;= n &lt;= 105</code></li>
	<li><code>0 &lt;= edges.length &lt;= 105</code></li>
	<li><code>edges[i].length == 3</code></li>
	<li><code>0 &lt;= fromi, toi, src1, src2, dest &lt;= n - 1</code></li>
	<li><code>fromi != toi</code></li>
	<li><code>src1</code>&nbsp;，<code>src2</code>&nbsp;和&nbsp;<code>dest</code>&nbsp;两两不同。</li>
	<li><code>1 &lt;= weight[i] &lt;= 105</code></li>
</ul>