SP14035 VPL1_AE - Winter Crush

冬天总让人感到悲伤，尤其是当你没有人陪伴的时候。情人节即将来临，Dickie 对 Elizabeth 一见钟情，但她用经典的“你是我最好的朋友”等说法把他打入了“朋友区”。 不过，Dickie 决定不再忍受这种状态。他计划在情人节那天进行一项绝对行动来赢得 Elizabeth 的芳心，并把这个计划称为“不再做备胎行动”。虽然具体细节还未敲定，因为它很大程度上取决于 Elizabeth 当天的位置。然而，Dickie 足够聪明，他已经找到了根据时间计算 Elizabeth 位置概率的方法。 作为 Elizabeth 的“最好朋友”，Dickie 深知她的喜好。他知道，当她处于某个位置 $x$ 时，会以一定概率 $p_{xy}$ 移动到相邻位置 $y$，这种概率取决于移动过程中获得的快乐和路径上的积雪。快乐值 $j_{xy}$ 以“快乐单位”衡量，积雪量 $s_{xy}$ 用厘米表示，选择的概率由 $\frac{j_{xy}}{s_{xy}}$ 计算。一些规则如下： - 所有位置的集合称为 $V$。 - 对于任何给定的 $x \in V$，与 $x$ 相邻的位置集合称为 $E_x$。位置 $y$ 被称为相邻位置，如果有路径从 $x$ 到 $y$。路径是双向的，因此 $\frac{j_{xy}}{s_{xy}} = \frac{j_{yx}}{s_{yx}}$。 - $\forall x \in V \land \forall y \in E_x$： $$ \sum_{y \in E_x} p_{xy} = 1 $$ Dickie 心中已经有了一些可以找到 Elizabeth 的位置，但他知道她可能从自己家或者朋友家出发。于是，他希望知道在给定的时间和出发位置下，哪个位置找到她的概率最大。他想评估几种潜在情况，因此每个查询由时间 $T_i$ 和若干出发位置 $P_i$ 组成。

第一行是整数 $C$，表示测试用例数量。接下来是 $C$ 个测试用例的描述。 每个测试用例以两个整数 $N$ 和 $M$ 开始，分别表示位置数量和路径数量。接下来的 $M$ 行，每行包含四个整数 $x, y, j_{xy}, s_{xy}$，如上述所述。所有位置的索引从 0 开始。接下来的第 $M + 1$ 行包含一个整数 $Q$，表示查询数量。每个查询由两个整数 $T_i$ 和 $q_i$ 开始，分别表示经过时间和可能的出发位置数量。接下来的 $q_i$ 行，每行包含一个整数 $P_i$，表示 Elizabeth 的出发位置。

对于每个测试用例，输出 `Scenario #i:`，其中 $i$ 是测试用例编号（从 1 开始），然后输出一行空行。对于每个输入的查询 $Q_i$，输出一行 $q_i$ 个整数，表示在给定时间 $T_i$ 和出发位置 $P_i$ 下，找到 Elizabeth 概率最大的那个位置。如果有多个位置具有相同的最大概率，输出最小的一个。如果所有位置概率均为 0，输出 `-1`。

- $0 < j_{xy}, s_{xy}$ - $0 \le T_i$ **子任务 1 (30%)** - $1 \le N \le 10$ - $1 \le M \le 20$ - $0 \le j_{xy}, s_{xy} \le 100$ - $1 \le Q \le 10$ - $q_i = 1$ - $0 \le T_i \le 100$ **子任务 2 (70%)** - $1 \le N \le 100$ - $1 \le M \le 200$ - $1 \le j_{xy}, s_{xy} \le 100$ - $2 \le Q \le 100$ - $1 \le q_i \le 5$ - $0 \le T_i \le 100000$ **本翻译由 AI 自动生成**