LC 1786. 从第一个节点出发到最后一个节点的受限路径数

题目描述

这是 LeetCode 上的 1786. 从第一个节点出发到最后一个节点的受限路径数 ，难度为 中等。

现有一个加权无向连通图。给你一个正整数 n ，表示图中有 n 个节点，并按从 1 到 n 给节点编号；另给你一个数组 edges，其中每个 $edges[i] = [u{i}, v{i}, weight{i}]$ 表示存在一条位于节点 $u{i}$ 和 $v{i}$ 之间的边，这条边的权重为 $weight{i}$ 。

从节点 start 出发到节点 end 的路径是一个形如 $[z{0}, z{1}, z{2}, …, z{k}]$ 的节点序列，满足 $z{0} = start$ 、$z{k} = end$ 且在所有符合 $0 <= i <= k-1$ 的节点 $z{i}$ 和 $z{i}+1$ 之间存在一条边。

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

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

示例 1：