调试中...
调试中...
题目描述
题目描述
题解
题解
提交记录
提交记录
代码
代码
测试用例
测试用例
测试结果
测试结果
中等
相关标签
相关企业
提示

现有一个加权无向连通图。给你一个正整数 n ,表示图中有 n 个节点,并按从 1n 给节点编号;另给你一个数组 edges ,其中每个 edges[i] = [ui, vi, weighti] 表示存在一条位于节点 uivi 之间的边,这条边的权重为 weighti

从节点 start 出发到节点 end 的路径是一个形如 [z0, z1, z2, ..., zk] 的节点序列,满足 z0 = startzk = end 且在所有符合 0 <= i <= k-1 的节点 zizi+1 之间存在一条边。

路径的距离定义为这条路径上所有边的权重总和。用 distanceToLastNode(x) 表示节点 nx 之间路径的最短距离。受限路径 为满足 distanceToLastNode(zi) > distanceToLastNode(zi+1) 的一条路径,其中 0 <= i <= k-1

返回从节点 1 出发到节点 n受限路径数 。由于数字可能很大,请返回对 109 + 7 取余 的结果。

 

示例 1:

输入:n = 5, edges = [[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
输出:3
解释:每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。三条受限路径分别是:
1) 1 --> 2 --> 5
2) 1 --> 2 --> 3 --> 5
3) 1 --> 3 --> 5

示例 2:

输入:n = 7, edges = [[1,3,1],[4,1,2],[7,3,4],[2,5,3],[5,6,1],[6,7,2],[7,5,3],[2,6,4]]
输出:1
解释:每个圆包含黑色的节点编号和蓝色的 distanceToLastNode 值。唯一一条受限路径是:1 --> 3 --> 7 。

 

提示:

  • 1 <= n <= 2 * 104
  • n - 1 <= edges.length <= 4 * 104
  • edges[i].length == 3
  • 1 <= ui, vi <= n
  • ui != vi
  • 1 <= weighti <= 105
  • 任意两个节点之间至多存在一条边
  • 任意两个节点之间至少存在一条路径
通过次数
7.7K
提交次数
20.4K
通过率
37.8%


相关企业

提示 1
Run a Dijkstra from node numbered n to compute distance from the last node.

提示 2
Consider all edges [u, v] one by one and direct them such that distance of u to n > distance of v to n. If both u and v are at the same distance from n, discard this edge.

提示 3
Now this problem reduces to computing the number of paths from 1 to n in a DAG, a standard DP problem.


评论 (0)

贡献者
© 2025 领扣网络(上海)有限公司
0 人在线
行 1,列 1
n =
5
edges =
[[1,2,3],[1,3,3],[2,3,1],[1,4,2],[5,2,2],[3,5,1],[5,4,10]]
Source