A89694.「2017 山东一轮集训 Day6」重建
省选/NOI-
通过率：0%
时间限制：1.00s
内存限制：512MB
题目描述
给定一个 $ 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} $。
输入输出样例
输入#1
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
输出#1
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 $。