|
Gi is a naughty child. He often does some strange things. Therefore, his father decides to play a game with him.?
Gi's father is a senior magician, he teleports Gi and Gi's Slipper into a labyrinth. To simplify this problem, we regard the labyrinth as a tree with?nn?nodes, rooted at node?11. Gi is initially at node?ss, and his slipper is at node?tt. In the tree, going through any edge between two nodes costs?ww?unit of power.?
Gi is also a little magician! He can use his magic to teleport to any other node, if the depth difference between these two nodes equals to?kk. That is, if two nodes?u,vu,vsatisfying that?∣depu?depv∣=k∣depu??depv?∣=k, then Gi can teleport from?uu?to?vv?or from?vv?to?uu. But each time when he uses magic he needs to consume?pp?unit of power. Note that he can use his magic any times.?
Gi want to take his slipper with minimum unit of power.
Input
Each test contains multiple test cases. The first line contains the number of test cases?(1≤T≤5)(1≤T≤5). Description of the test cases follows.?
The first line contains an integer?nn?--- The number of nodes in the tree.?2≤n≤1062≤n≤106.?
The following?n?1n?1?lines contains 3 integers?u,v,wu,v,w?that means there is an edge between nodes?uu?and?vv. Going through this edge costs?ww?unit of power.?1≤u,v≤n,1≤w≤1061≤u,v≤n,1≤w≤106.?
The next line will contain two separated integers?k,pk,p.?1≤k≤max?u?V(depu),0≤p≤1061≤k≤maxu?V?(depu?),0≤p≤106.?
The last line contains two positive integers?s,ts,t, denoting the positions of Gi and slipper.?1≤s≤n,1≤t≤n1≤s≤n,1≤t≤n. It is guaranteed the?s≠ts=t.
Output
For each test case:?
Print an integer in a line --- the minimum unit of power Gi needs.
Sample
| Input | Output |
|---|
1
6
6 1 2
3 5 2
2 4 6
5 2 2
5 6 20
3 8
6 5 |
12 |
题意：?给出一棵n点构成的树，树上每条边都有边权wi，表示移动所需的能量，对于深度差为k的点还可以通过花费p点能量传送过去，给出起点s和终点t，问从起点到达终点所需最少能量。
分析：?一开始想到的是对于深度差为k的点对建边，但是由于这两层之间任意两点都需要一条连边，显然会添加很多条边，这样跑最短路就会TLE，一个更好的思路是对于这两层建立一个虚点，各层上的点都连到虚点上，这样就会少添加很多边，不过还需要注意不能只用一个虚点，对于向上传送建立一个虚点，对于向下传送还需要建立一个虚点，这是为了防止利用传送在同层间任意转移。
建好图后直接跑一个dijkstra就ok了，最后要注意用vector数组建图会MLE，这可能与vector动态申请空间有关，用vector邻接表错了的可以换成链式前向星试试。
具体代码如下：
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <vector>
#include <queue>
#define inf 0x3f3f3f3f3f3f3f3f
#define pii pair<long long, int>
using namespace std;
struct edge{
int to, next, w;
}e[1000005*4];
int head[1000005*3];
long long dis[1000005*3];
int n, k, s, t, p, cnt;
bool vis[1000005*3];
vector<int> P[1000005];
void add(int u, int v, int w){
e[++cnt].to = v;
e[cnt].w = w;
e[cnt].next = head[u];
head[u] = cnt;
}
void dfs(int now, int fa, int h){
P[h].push_back(now);
for(int i = head[now]; i; i = e[i].next){
int to = e[i].to;
if(to == fa) continue;
dfs(to, now, h+1);
}
}
void dijkstra(){
priority_queue<pii, vector<pii>, greater<pii> >q;
dis[s] = 0;
q.push(make_pair(dis[s], s));
while(q.size()){
int now = q.top().second;
q.pop();
if(now == t) return;
if(vis[now]) continue;
vis[now] = true;
for(int i = head[now]; i; i = e[i].next){
int to = e[i].to;
int w = e[i].w;
if(dis[to] > dis[now]+w){
dis[to] = dis[now]+w;
q.push(make_pair(dis[to], to));
}
}
}
}
signed main()
{
int T;
cin >> T;
while(T--){
scanf("%d", &n);
cnt = 0;
for(int i = 1; i <= 3*n; i++){
head[i] = 0;
dis[i] = inf;
vis[i] = false;
}
for(int i = 1; i <= n+1; i++)
P[i].clear();
for(int i = 1; i < n; i++){
int u, v, w;
scanf("%d%d%d", &u, &v, &w);
add(u, v, w);
add(v, u, w);
}
scanf("%d%d%d%d", &k, &p, &s, &t);
dfs(1, 0, 1);
for(int i = k+1; P[i].size() != 0; i++){
int n1 = ++n;//从上层向下层传输
int n2 = ++n;//从下层向上层传输
for(int j = 0; j < P[i].size(); j++){
add(n1, P[i][j], 0);
// g[n1].push_back(make_pair(0, P[i][j]));
add(P[i][j], n2, 0);
// g[P[i][j]].push_back(make_pair(0, n2));
}
for(int j = 0; j < P[i-k].size(); j++){
add(n2, P[i-k][j], p);
// g[n2].push_back(make_pair(p, P[i-k][j]));
add(P[i-k][j], n1, p);
// g[P[i-k][j]].push_back(make_pair(p, n1));
}
}
dijkstra();
printf("%lld\n", dis[t]);
}
return 0;
}
|