← 返回题目
题库练习 「2017 山东一轮集训 Day6」重建
← 上一题 下一题 →

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

时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

给定一个 $ 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
C++ 编辑器
输入
输出