#P18061. Bobs Rating
Bobs Rating
Bobs Rating
给定一个有 个顶点、 条边的无向图。第 条边连接 ,通行所需的评级为 。图可能不连通,允许自环和重边。
Bob 可以任意重复经过边、访问顶点。当且仅当他的当前评级至少为 时,他才能经过第 条边;经过边不会消耗评级。
当 Bob 位于顶点 时,可以进行以下操作:
- 免费增加 点评级。在一次旅程中,每个顶点的这项免费奖励只能领取一次;不同顶点的免费奖励分别计算。
- 花费 枚金币增加 点评级。这项操作可以重复任意次。
有 次相互独立的询问。第 次询问中,Bob 初始位于 ,评级为 ,希望到达 。求所需的最少金币数。出发时也可以领取起点的免费奖励。
如果无论花费多少金币都不能到达目标,输出 。
输入格式
第一行一个整数 ,表示测试用例数。
每组数据包含:
- 第一行三个整数 。
- 第二行 个整数 。
- 第三行 个整数 。
- 接下来 行,每行三个整数 。
- 接下来 行,每行三个整数 。
输出格式
每组数据输出 行,每行一个整数,依次回答各次询问。
数据范围
,,,。
所有顶点编号在 到 之间。跨所有测试用例,、、 各自不超过 。
样例
1
5 5 4
5 2 4 3 10
1 2 3 4 5
3 3 10
1 2 5
3 4 7
1 3 13
2 5 21
4 5 3
2 2 4
1 4 2
5 2 10
11
0
4
5