P13300 [GCJ 2013 #3] Are We Lost Yet?

现在是 Google Code Jam 总决赛的时间了，我们都希望能够到场！不幸的是，我们中的几个人却误打误撞去了 Mountain View，而不是正确的地点伦敦。不过别担心——我们可以乘坐 Google 提供的免费穿梭巴士从 Mountain View 前往伦敦！ 这项巴士服务由 $M$ 条单向路线组成，连接着不同的城市。对于每一条路线，你知道它是从哪座城市出发、到达哪座城市，但你并不知道这条路线的具体长度。你只知道每条路线的长度可以是从 $a_i$ 到 $b_i$（包含两端）的任意整数值。 我曾多次乘坐 Google 的穿梭巴士，因此我为你规划了一条从 Mountain View 到伦敦的路线。但你担心我的路径规划能力不如你，所以你想检查一下我的方案。 给定我建议的这条路径，它是否有可能是 Mountain View 到伦敦的最短路径？如果不是，那么请指出在我的路径上第一个**肯定不可能**属于最短路径的穿梭巴士路线的编号（假设在此之前的所有路线都已按照我建议的路径依次乘坐）。 例如，假设有如下穿梭路线列表： | 路线编号 | 起点城市 | 终点城市 | 路线长度 | | :-: | :-: | :-: | :-: | | 1 | Mountain View | London | $[100, 1000]$ | | 2 | Mountain View | Paris | $[500, 5000]$ | | 3 | Paris | London | $[400, 600]$ | | 4 | Paris | Moscow | $[500, 5000]$ | | 5 | Moscow | London | $[1, 10000]$ | 我建议的路径为 Mountain View -> Paris -> Moscow -> London。实际上，最短路径可能是直接从 Mountain View 到 London，也可能是 Mountain View -> Paris -> London。这意味着我建议的路径上第二段（Paris -> Moscow）就是第一个**肯定不可能**属于最短路径的穿梭路线。

输入的第一行为测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为三个正整数 $N$、$M$、$P$，分别表示城市总数（城市编号为 $1$ 到 $N$）、穿梭路线总数、以及我建议的路径上穿梭路线的数量（从 Mountain View（城市 $1$）到 London（城市 $2$））。 接下来 $M$ 行，每行四个整数 $u_i$、$v_i$、$a_i$、$b_i$，表示有一条从城市 $u_i$ 到城市 $v_i$ 的单向穿梭路线，其长度可以是 $a_i$ 到 $b_i$ 之间的任意整数。穿梭路线的编号为 $1$ 到 $M$，顺序与输入一致。 接下来一行包含 $P$ 个不同的整数，范围为 $1$ 到 $M$，依次表示我建议的路径上经过的穿梭路线编号。

对于每个测试用例，输出一行 `"Case #x: n"`，其中 $x$ 为测试用例编号（从 $1$ 开始），$n$ 为我的路径上第一个肯定不可能属于最短路径的穿梭路线编号。如果所有路线都有可能属于最短路径，则输出 `"Looks Good To Me"`。

**限制条件** - 我的路径保证是从 Mountain View（城市 $1$）到 London（城市 $2$）的一条合法路径。 - 可能会有多条路线连接同一对城市，也可能有从某城市到自身的路线。建议的路径可能会多次经过同一城市，但不会重复使用同一条路线。 **小数据集（12 分，测试集 1 - 可见）** - $2 \leq N \leq 20$ - $1 \leq M \leq 20$ - $1 \leq P \leq 10$ **大数据集（18 分，测试集 2 - 隐藏）** - $2 \leq N \leq 1000$ - $1 \leq M \leq 2000$ - $1 \leq P \leq 500$ 翻译由 ChatGPT-4.1 完成。