[2022 Hangzhou Electric Multi-School 5 1003 Slipper] Multiple Super Source Points + Shortest Path

题目描述

输入

输出

样例输入

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

样例输出

12

题意

一棵树,Each edge has a weight,然后可以以pThe cost is transmitted to the distance from the current nodek层的任意节点,pis given by the input,Now give you a starting point and an ending point,Ask what is the shortest cost from start to finish.

思路

In addition to being able to transmit this condition, it is a shortest path,if the distancekIf each point of the layer is built with an edge, then there are too many edges,Then you can think of building a super source point at each layer,The distance of this super source point from the point of this layer is 0,and distance this layer iskThe distance of the super source point is p,然后wa掉了,Because only one super source point is established, the distance between any two points on the same layer will become 0,这是不成立的,Then you can build two super source points per layer,一个进,一个出,这样问题就迎刃而解了,Let's take a look at this sample image first,The blue dots on each layer are the out points,The red dot is the entry point.下面看代码吧：

#include<bits/stdc++.h>
using namespace std;
const int N = 5e6+10;
typedef long long LL;
int h[N],e[N+N],ne[N+N];
int w[N+N],idx;
void add(int a,int b,int c){
    
	e[idx] = b;
	w[idx] = c;
	ne[idx] = h[a];
	h[a] = idx++;
}
vector<int> de[N];
int n,k,p;
LL dis[N];
bool st[N];
int mx;
void dfs(int u,int fa,int deep){
    
	de[deep].push_back(u);
	mx = max(mx,deep);
	for(int i=h[u];i!=-1;i=ne[i]){
    
		int v = e[i];
		if(v == fa) continue;
		dfs(v,u,deep+1);
	}
}
typedef pair<LL,int> PII;
void solve(){
    
	scanf("%d",&n);
	idx = 0;
	mx = 0;
	for(int i=1;i<=4*n;i++){
    
		h[i] = -1;
		dis[i] = 0x3f3f3f3f3f3f3f3fll;
		de[i].clear();
		st[i] = false;
	}
	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",&k,&p);
	dfs(1,0,1);
	for(int i=1;i<=mx;i++){
    
		for(auto u : de[i]){
    
			add(u,n+i*2-1,0);
			add(i*2+n,u,0);
		}
		if(i+k>mx) continue;
		add(n+i*2-1,n+(i+k)*2,p);
		add(n+(i+k)*2-1,n+i*2,p);
	}
	int sta,ed;
	scanf("%d%d",&sta,&ed);
	priority_queue<PII,vector<PII>,greater<PII> > q;
	dis[sta] = 0;
	q.push(make_pair(0,sta));
	while(q.size()){
    
		int t = q.top().second;
		q.pop();
		if(st[t]) continue;
		if(t == ed) break;
		st[t] = true;
		for(int i=h[t];i!=-1;i=ne[i]){
    
			int j = e[i];
			if(dis[j] > dis[t] + w[i]){
    
				dis[j] = dis[t] + w[i];
				if(!st[j]) q.push({
    dis[j],j});
			}
		}
	}
	printf("%lld\n",dis[ed]);
}
int main(){
    
	int _;
	scanf("%d",&_);
	while(_--) solve();
	return 0;
}