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

    ID: 7244 传统题 1000ms 512MiB 尝试: 4 已通过: 2 难度: 7 上传者: 标签>CF2200提高线性 DP滚动数组暴力枚举向下取整与向上取整

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

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

题目描述

给定一个有 nn 个点、mm 条边的带权无向图 GG,以及 kk 个关键点编号。点的编号为 1∼n1\sim n。

有一个人要从点 ss 走到点 tt。现在可以选择一个非负整数 cc,并把图中每一条边的边权都增加 cc。

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

  • 从 ss 到 tt 的普通最短路;
  • 从 ss 到 tt,并且路径上经过的所有顶点都必须是关键点的最短路。

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

如果不存在任何合法的非负整数 cc,输出 Impossible;如果合法的 cc 可以任意大,输出 Infinity。

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

输入格式

第一行一个整数 TT,表示测试数据组数。

对于每组测试数据:

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

接下来 mm 行,每行三个整数 ui,vi,wiu_i,v_i,w_i,表示一条连接 uiu_i 与 viv_i、边权为 wiw_i 的无向边。

接下来一行一个整数 kk。

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

输出格式

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

  • 若存在最大的合法非负整数 cc,输出这个整数;
  • 若不存在合法的 cc,输出 Impossible;
  • 若任意大的 cc 都可以满足条件,输出 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%20\% 的数据,n,m,wi≤100n,m,w_i\le 100。

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

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

对于全部数据:

  • 1≤T≤31\le T\le 3;
  • 1≤n≤10001\le n\le 1000;
  • 1≤m≤100001\le m\le 10000;
  • 1≤s,t≤n1\le s,t\le n;
  • 0≤wi≤1090\le w_i\le 10^9;
  • 1≤k≤n1\le k\le n;
  • 每个给出的关键点编号均在 [1,n][1,n] 内;
  • s,ts,t 均为关键点;
  • 保证 ss 与 tt 在原图中可达。