#P18577. Transfers in a Cactus Graph
Transfers in a Cactus Graph
Transfers in a Cactus Graph
某个交通网络中的每个顶点都是一个换乘枢纽。当你位于顶点 时,可以购买一张前往任意另一个顶点 的车票。这张车票的价格为
其中 是网络原图中 与 之间的最短路长度。抵达 后,你可以立即结束旅程,也可以从 购买下一张车票。换乘次数没有限制。整个旅程的费用是所有已购车票的价格之和。
交通网络是一个连通、无向、带权的仙人掌图,即每条边至多属于一个简单环。图有 个顶点、 条边,第 条边的长度为 。每个顶点 的参数为 。
请对每个顶点 ,求出从顶点 到顶点 的旅程的最小费用。
输入格式
第一行一个整数 ,表示测试用例数,。
每个测试用例的第一行包含两个整数 ,满足 ,。
接下来 行描述边。每行三个整数 ,表示一条连接 和 、长度为 的双向边,,。
保证图连通、是仙人掌图,且无自环、无重边。
接下来 行,第 行包含两个整数 ,其中 ,。
所有测试用例的 之和不超过 , 之和不超过 。
输出格式
对每个测试用例输出一行 个整数,第 个整数是从顶点 到顶点 的最小旅程费用。顶点 的答案为 。
原样例
2
3 2
1 2 5
2 3 4
10 1
20 2
30 5
3 2
1 2 5
2 3 5
0 10
1 1
100 10
0 15 19
0 50 56