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

题目描述

给定一个有 $n$ 个点、$m$ 条边的带权无向图 $G$，以及 $k$ 个关键点编号。点的编号为 $1\sim n$。

有一个人要从点 $s$ 走到点 $t$。现在可以选择一个非负整数 $c$，并把图中每一条边的边权都增加 $c$。

对于修改后的图，考虑下面两种最短路：

• 从 $s$ 到 $t$ 的普通最短路；
• 从 $s$ 到 $t$，并且路径上经过的所有顶点都必须是关键点的最短路。

求最大的非负整数 $c$，使得这两种最短路的长度相等。

如果不存在任何合法的非负整数 $c$，输出 Impossible；如果合法的 $c$ 可以任意大，输出 Infinity。

输入中给出的 $k$ 个关键点编号可能出现重复；重复编号视为同一个关键点。保证 $s$ 和 $t$ 都是关键点，并保证原图中 $s$ 与 $t$ 可达。图中可能存在与 $s,t$ 所在连通块无关的顶点。

输入格式

第一行一个整数 $T$，表示测试数据组数。

对于每组测试数据：

第一行四个整数 $n,m,s,t$。

接下来 $m$ 行，每行三个整数 $u_i,v_i,w_i$，表示一条连接 $u_i$ 与 $v_i$、边权为 $w_i$ 的无向边。

接下来一行一个整数 $k$。

接下来给出 $k$ 个整数，表示关键点编号。它们之间可以由任意空白字符分隔。

输出格式

对于每组测试数据输出一行：

• 若存在最大的合法非负整数 $c$，输出这个整数；
• 若不存在合法的 $c$，输出 Impossible；
• 若任意大的 $c$ 都可以满足条件，输出 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,w_i\le 100$。

对于 $40\%$ 的数据，$n,m\le 100$。

另外有 $20\%$ 的数据，每组测试的答案一定为 Infinity 或 Impossible。

对于全部数据：

• $1\le T\le 3$；
• $1\le n\le 1000$；
• $1\le m\le 10000$；
• $1\le s,t\le n$；
• $0\le w_i\le 10^9$；
• $1\le k\le n$；
• 每个给出的关键点编号均在 $[1,n]$ 内；
• $s,t$ 均为关键点；
• 保证 $s$ 与 $t$ 在原图中可达。