leetcode在力扣 App 中打开
调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
困难
相关标签
相关企业
提示

给你一个整数 n ,它表示一个 带权有向 图的节点数,节点编号为 0 到 n - 1 。

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

最后,给你三个 互不相同 的整数 src1 ,src2 和 dest ,表示图中三个不同的点。

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

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

 

示例 1:

输入: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]] 也能得到最优解,但无法在满足所有限制的前提下,得到更优解。

示例 2:

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

 

提示:

  • 3 <= n <= 105
  • 0 <= edges.length <= 105
  • edges[i].length == 3
  • 0 <= fromi, toi, src1, src2, dest <= n - 1
  • fromi != toi
  • src1 ,src2 和 dest 两两不同。
  • 1 <= weight[i] <= 105
通过次数
5.2K
提交次数
13.4K
通过率
38.6%

相关标签

相关企业

提示 1
Consider what the paths from src1 to dest and src2 to dest would look like in the optimal solution.

提示 2
It can be shown that in an optimal solution, the two paths from src1 and src2 will coincide at one node, and the remaining part to dest will be the same for both paths. Now consider how to find the node where the paths will coincide.

提示 3
How can algorithms for finding the shortest path between two nodes help us?


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
Sales =
| sale_id | product_id | year | quantity | price | | ------- | ---------- | ---- | -------- | ----- | | 1 | 100 | 2008 | 10 | 5000 | | 2 | 100 | 2009 | 12 | 5000 | | 7 | 200 | 2011 | 15 | 9000 |
Product =
| product_id | product_name | | ---------- | ------------ | | 100 | Nokia | | 200 | Apple | | 300 | Samsung |
Source
重置测试用例