「2017 山东一轮集训 Day6」重建

传统 1000 ms 512 MiB

$62$ 通过 $174$ 提交

题目描述

给定一个 $n$ 个点 $m$ 条边的带权无向连通图 $G$，以及一个大小为 $k$ 的关键点集合 $A$。有个人要从点 $s$ 走到点 $t$，现在可以对所有边加上一个非负整数 $c$，问最大的 $c$，使得加上 $c$ 后，满足：$s$ 到 $t$ 的最短路长度 = $s$ 到 $t$ 且只能经过 $A$ 中的点的最短路长度。

输入格式

第一行一个整数 $T$。代表这个数据点中有 $T$ 个测试数据。

对于每个测试数据： 第一行包含四个整数 $n, m, s, t$。 接下来 $m$ 行，每行三个整数 $u_i, v_i, c_i$，代表 $G$ 中有一条 $u_i$ 到 $v_i$ 的长度为 $c_i$ 的无向边。 第 $m + 1$ 行包含一个整数 $k$。 接下来一行 $k$ 个整数，代表关键点集合 $A$。保证 $s$ 与 $t$ 都在 $A$ 中。

输出格式

对于每个测试数据，输出一行一个整数 $c$，代表最大的合法的加到每条边的权值。假如不存在这样的合法的 $c$，则输出 $\texttt{Impossible}$，假如这样的 $c$ 可以无穷大，则输出 $\texttt{Infinity}$。

样例

输入

3
6 8 1 6
1 2 5
1 3 1
2 6 6
2 3 6
4 2 3
3 4 1
4 5 1
5 6 1
5
1 3 6 5 4
3 4 1 2
1 2 6
1 3 2
1 2 7
2 3 3
2
1 2
4 4 1 4
1 2 1
1 3 1
2 4 1
3 4 1
3
1 2 4

输出

3
Infinity
Infinity

数据范围与提示

对于 $20\%$ 的数据，$n, m, c_i \leq 100$；
对于 $40\%$ 的数据，$n, m \leq 100$；
另外有 $20\%$ 的数据，每个测试数据的答案要么为 $\texttt{Infinity}$，要么为 $\texttt{Impossible}$；
对于 $100\%$ 的数据，满足 $1 \leq n \leq 1000$，$1 \leq m \leq 10000$，$1 \leq c_i \leq 10^9$，$1 \leq T \leq 3$。