P13236 [GCJ 2015 Finals] Taking Over The World

你和你的朋友 Pinky 有一个征服世界的计划。但首先，你们需要关闭一个秘密武器。 这个武器被藏在一个错综复杂的迷宫（一个图）中，只有一个入口。Pinky 将会在有秘密武器的房间（顶点）里关闭它。与此同时，安全小队会在图的入口处被警报唤醒，并试图穿过图去阻止 Pinky。你要尽可能拖慢安全小队的速度，为 Pinky 争取时间。通过任意一条边都需要 1 个时间单位，但你还可以“阻碍”最多 $K$ 个顶点。每经过一个被阻碍的顶点，需要额外花费 1 个时间单位。你需要选择一组顶点进行阻碍，使得安全小队到达秘密武器房间所需的时间尽可能长。 安全小队会从图的入口出发，目标是到达秘密武器房间。你需要在安全小队开始行动前就决定所有要阻碍的顶点，且安全小队会知道你阻碍了哪些顶点，并会选择最优路径。 阻碍秘密武器房间没有意义，因为当安全小队到达那里时，Pinky 已经被抓住，无法再拖延时间。另一方面，阻碍入口显然是一个好主意。

输入的第一行是测试用例数 $T$。接下来有 $T$ 组测试数据。每组测试数据的第一行为 $N, M, K$。接下来的 $M$ 行，每行包含一对顶点，表示一条边。顶点编号从 $0$（入口）到 $N-1$（秘密武器房间）。每对顶点中，第一个编号总是小于第二个编号，并且同一组测试数据中不会有重复的边。所有边都是双向的——安全小队可以沿任意方向通过。

对于每组测试数据，输出一行，格式为 "Case #x: y"，其中 $x$ 是测试用例编号（从 1 开始），$y$ 是安全小队从入口到秘密武器房间所需的时间。

**数据范围** - $1 \leq T \leq 100$。 - $2 \leq N \leq 100$。 - $1 \leq M \leq N \times (N - 1) / 2$。 - $1 \leq K \leq N$。 - 保证从房间 0 到房间 $N-1$ 总是存在一条路径。 **小数据集（7 分）** - 时间限制：5 秒。 - 使用给定的 $K$，安全小队最多只能被延迟 2 个时间单位（相较于最短未阻碍路径）。 **大数据集（29 分）** - 时间限制：10 秒。 - 无额外限制。 由 ChatGPT 4.1 翻译