最短路

时间限制: 5000 ms 内存限制: 131072 kb
总通过人数: 10 总提交人数: 20

题目描述

一棵 $n$ 个点的有根树,以 $1$ 号点为根,走一条边需要花费相应的代价,任意深度相差为 $1$ 的点之间可以相互跳跃,花费代价为 $p$ ,求 $s$ 走到 $t$ 的最小代价。

输入

第一行包含一个整数 $T$ ,表示数据组数。

对于每组数据,包含若干行,第一行四个整数 $n,p,s,t$,意义见题目描述。 接下来 $n-1$ 行描述这棵树,每行三个整数 $u,v,w$,表示走一条连接 $u$ 和 $v$ 号点的边的代价为 $w$ 。

其中,$1\le T\le 20$,$1\le n\le 10^5,1\le s,t,u,v \le n,0\le p,w \le 10^9$

输出

对于每组数据,输出一行,格式为 Case #number: result,其中 $\mathrm{number}$ 表示这是第 $\mathrm{number}$ 组数据,而 $\mathrm{result}$ 为答案。

输入样例

2
2 1 1 2
1 2 3
7 999999999 2 7
1 2 1000000000
1 3 1000000000
2 4 999999998
3 5 1000000000
5 6 1000000000
6 7 999999998

输出样例

Case #1: 1
Case #2: 2999999995

相关推荐