SP11771 RPLM - Mountain Cave

查理在一座因其珍贵宝石而著名的洞穴中采集石头。这个洞穴的结构非常脆弱，一点小动作就可能导致洞穴坍塌。然而，查理知道何时隧道会被石堆覆盖或重新开放。 查理的背包中装有一些用来应急的魔法锤子。在某些探险中，他可能没有锤子，但在另一些情况下他会携带这些锤子。锤子可以用来瞬间清除挡路的石堆。 在这个场景中，查理知道从房间 $i$ 到房间 $j$ 的距离为 $d$，需要的时间是 $t$，且连接这两个房间的隧道在时间 $x$ 到 $y$ 之间是畅通的。查理可以随时返回原点，因此从房间 $j$ 到房间 $i$ 也适用同样的规则。 查理携带的锤子数量有限，一旦用了就失去作用。此外，若查理知道一条隧道将在某个时间 $X$ 开放，他可以选择等待隧道开放，或者使用魔法锤子直接通过。 你的任务是计算查理从入口（编号为0的房间）到洞穴中心（编号为 $V-1$ 的房间）所用的最短时间和对应的最短距离。

输入的第一行是一个整数 $T$，表示有 $T$ 组测试用例。接下来的每一组测试用例开始于一行，包含三个整数 $V$、$E$ 和 $M$，分别代表洞穴中的房间数量、隧道数量以及查理携带的锤子数量。接下来的 $E$ 行，每行包括六个整数 $i$、$j$、$x$、$y$、$z$ 和 $t$，分别表示起始房间 $i$、目标房间 $j$、隧道开放时间 $x$、关闭时间 $y$、距离 $z$ 和旅行所需时间 $t$。

对于每组测试用例，输出应为字符串“Scenario #i: ”，其中 $i$ 是测试用例的编号，后面接表示最短时间和对应的最短距离的两个整数。如果查理无法到达编号为 $V-1$ 的房间，则输出 -1。

- $1 \le T \le 10$ - 小规模输入：(20%) - $2 \le V \le 10$ - $1 \le E \le 30$ - $M = 0$ - 中等规模输入：(30%) - $2 \le V \le 100$ - $1 \le E \le 1,000$ - $M = 0$ - 大规模输入：(50%) - $2 \le V \le 100$ - $1 \le E \le 1,000$ - $0 \le M \le 50$ 可以确保隧道距离不会超过 10。 - $1 \le$ 隧道开放时间和关闭时间 $\le 100,000$ **说明：** 你的旅程从时间 0 开始。始终满足条件：时间 $x$ 小于或等于时间 $y$。如果在穿越隧道的过程中隧道崩塌，你可以用锤子劈开，否则该路径将无法通行。 **本翻译由 AI 自动生成**