P16860 [GKS 2021 #F] Graph Travel
题目描述
Ada 住在一个魔法国家 $A$，她在魔法大学学习。今天，Ada 想在一个特殊空间中收集魔法点。
这个空间有 $N$ 个房间（编号 $0, 1, \ldots, N - 1$）。有 $M$ 条走廊连接这些房间。走廊 $j$ 连接房间 $X_j$ 和 $Y_j$，即你可以在两个房间之间移动。
第 $i$ 个房间包含 $A_i$ 个魔法点，并且受到一个具有属性 $L_i$ 和 $R_i$ 的魔法护盾的保护。要进入第 $i$ 个房间，首先你需要通过已经破盾的房间到达与第 $i$ 个房间相邻的任意房间（即通过走廊相连的房间）。然后你必须打破该房间的护盾，但只有当你的魔法点数在 $L_i$ 和 $R_i$ 之间（包含两端）时，你才能打破护盾。打破护盾后，你将进入该房间并自动收集该房间的 $A_i$ 个魔法点。房间不会生成新的魔法点。护盾被打破后也不会再生，因此无论你当前有多少点数，你都可以自由返回所有已经破盾的房间。
Ada 开始时拥有 $0$ 个魔法点，她的目标是找到一种方法恰好收集 $K$ 个魔法点。她可以在任意房间开始，也可以在任意房间结束。她选择的起始房间的魔法护盾会自动被打破，并且她会自动收集该房间的所有魔法点。
在查看了房间和走廊的地图后，Ada 认为任务太简单了，因此她想挑战一个更困难的任务：她想知达到目标有多少种不同的方式。如果两条路径的**唯一路径**不同，则认为它们是不同的。唯一路径是指她打破护盾的房间顺序（去除重复），例如：如果你按顺序访问房间 $(1, 3, 2, 1, 3, 5, 3, 6)$，则唯一路径为 $(1, 3, 2, 5, 6)$。
输入格式
输入的第一行给出测试用例的数量 $T$。接下来有 $T$ 个测试用例。
每个测试用例的第一行包含三个整数 $N$、$M$ 和 $K$：房间的数量、走廊的数量以及要收集的魔法点数。
接下来的 $N$ 行，每行包含三个整数 $L_i$、$R_i$ 和 $A_i$：第 $i$ 个房间的魔法护盾属性 $L_i$ 和 $R_i$，以及该房间的魔法点数 $A_i$。
接下来的 $M$ 行，每行包含两个整数 $X_j$ 和 $Y_j$：走廊 $j$ 连接的两个房间。
输出格式
对于每个测试用例，输出一行，格式为 `Case #x: y`，其中 $x$ 是测试用例编号（从 $1$ 开始），$y$ 是收集 $K$ 个魔法点的方式数量。
说明/提示
在第一个测试用例中，有 $4$ 种不同的方式，如下图所示：
:::align{center}
:::
在第二个测试用例中，有 $8$ 种不同的方式，如下图所示：
:::align{center}
:::
在第三个测试用例中，有 $4$ 种不同的方式，如下图所示：
:::align{center}
:::
### 限制条件
$1 \le T \le 100$。
$0 \le M \le \frac{N \times (N-1)}{2}$。
$0 \le X_j, Y_j \le N - 1$。
$X_j \ne Y_j$。
每对房间之间至多有一条走廊。
**测试集 1**
$1 \le N \le 8$。
$1 \le K \le 100$。
$0 \le L_i \le R_i \le 50$。
$1 \le A_i \le 50$。
**测试集 2**
$1 \le N \le 15$。
$1 \le K \le 2 \times 10^9$。
$0 \le L_i \le R_i \le 10^9$。
$1 \le A_i \le 10^9$。
翻译由 DeepSeek V4 Pro 完成