#P9174. Slipper

    ID: 5256 传统题 5000ms 256MiB 尝试: 2 已通过: 2 难度: 5 上传者: 标签>CF1800普及+/提高-辅助点压缩边Dijkstra广度优先搜索二叉堆2022

Slipper

Slipper

题目描述

Gi 是一个淘气的孩子,经常做一些奇怪的事情。因此,他的父亲决定和他玩一个游戏。

Gi 的父亲是一位资深魔法师,他把 Gi 和 Gi 的拖鞋传送进了一座迷宫。为了简化问题,我们将迷宫视为一棵有 nn 个节点、以节点 11 为根的树。记 depudep_u 为节点 uu 的深度。Gi 最初位于节点 ss,他的拖鞋位于节点 tt。在树上经过一条边需要消耗 ww 单位能量。

Gi 也是一位小魔法师!如果两个节点的深度之差等于 kk,他就可以使用魔法在这两个节点之间传送。也就是说,对于满足 ∣depu−depv∣=k|dep_u-dep_v|=k 的两个节点 u,vu,v,Gi 可以从 uu 传送到 vv,也可以从 vv 传送到 uu。每次使用魔法需要消耗 pp 单位能量。魔法的使用次数不限。

Gi 希望以最少的能量拿到他的拖鞋。

输入格式

输入包含多组测试数据。第一行包含测试数据组数 TT,其中 1≤T≤51\le T\le 5。

对于每组测试数据:

第一行包含一个整数 nn,表示树的节点数,2≤n≤1062\le n\le 10^6。

接下来 n−1n-1 行,每行包含三个整数 u,v,wu,v,w,表示节点 uu 和 vv 之间有一条边,经过这条边需要消耗 ww 单位能量。其中 1≤u,v≤n1\le u,v\le n,1≤w≤1061\le w\le 10^6。

接下来一行包含两个整数 k,pk,p,其中 1≤k≤max⁡1≤u≤ndepu1\le k\le \max_{1\le u\le n} dep_u,0≤p≤1060\le p\le 10^6。

最后一行包含两个正整数 s,ts,t,分别表示 Gi 和拖鞋的位置。其中 1≤s≤n1\le s\le n,1≤t≤n1\le t\le n,保证 s≠ts\ne t。

输出格式

对于每组测试数据,输出一行一个整数,表示 Gi 所需消耗的最少能量。

样例

1
6
6 1 2
3 5 2
2 4 6
5 2 2
5 6 20
3 8
6 5
12

提示

样例 1:Gi 可以先从节点 66 走到节点 11,消耗 22 单位能量。然后从节点 11 传送到节点 22,消耗 88 单位能量。最后从节点 22 走到节点 55,消耗 22 单位能量。

总消耗为 2+8+2=122+8+2=12。

来源:2022 中国大学生程序设计暑期联赛第 5 场(福州大学)。

原 PDF 题面