Slipper - virtual point, shortest path

Slipper

题意
The given root node is 1,节点数为 $n$ 的一棵树,n-1 side right $w_i$.
如果两个点 $u,v$ The difference in depth is $k(|de{p}_u-de{p}_v|=k)$ ,can reach each other directly,花费为 $p$.
给定起点和终点,Ask the minimum cost from start to finish.

$2\le n\le 10^6,1\le u,v\le n,1\le w\le 10^6.$
$1\le k\le ma{x}_u\subseteq V(de{p}_u),0\le p\le 10^6.$

思路
cost between two layers of nodes p 直接到达,Then you can connect.
But if you connect directly,Assume that two points, respectively n, m,Then the number of edges is n*m,边数很多.

Can it be less connected?？
Create an imaginary point between the two layers,All nodes in the upper layer are connected to the virtual point with a by-direction edge,边权为 p;Connect a directed edge from the virtual point to all nodes in the lower layer,边权为 0.连边数 n+m.
注意是有向边！
Then the cost from any node in the upper layer to any node in the lower layer is still p,But less to build a multilateral！

This is the idea,A virtual point is established between the two layers that can be directly reached,Two layers of nodes connect edges to this virtual point,Then you can run the shortest way directly.

需要注意,input quantity arrives 5e6,要换scanf,best read.

Code

#include<bits/stdc++.h>
using namespace std;

#define Ios ios::sync_with_stdio(false),cin.tie(0)
#define int long long
#define PII pair<int,int>
#define pb push_back
#define fi first
#define se second
#define endl '\n'

static char buf[100000],*pa=buf,*pd=buf;
#define gc pa==pd&&(pd=(pa=buf)+fread(buf,1,100000,stdin),pa==pd)?EOF:*pa++
inline int read()
{
    
    register int x(0);register char c(gc);
    while(c<'0'||c>'9')c=gc;
    while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=gc;
    return x;
}

const int N = 1000010, mod = 1e9+7;
int T, n, m;
int a[N];
vector<PII> e[N*2];
int k, p, st, en;
int dep[N];
vector<int> v[N];
int maxdep;
int dist[N*2], f[N*2];

void bfs()
{
    
	for(int i=1;i<=n;i++) dep[i] = 0;
	dep[1] = 1;
	queue<int> que;
	que.push(1);
	v[1].push_back(1);
	
	while(que.size())
	{
    
		int x = que.front(); que.pop();
		
		for(PII it : e[x])
		{
    
			int tx = it.fi;
			if(dep[tx]) continue;
			dep[tx] = dep[x] + 1;
			v[dep[tx]].push_back(tx);
			maxdep = max(maxdep, dep[tx]); //Maximum depth can be maintained,to reduce subsequent initialization and edge building 
			que.push(tx);
		}
	}
}

int dij()
{
    
	for(int i=1;i<=2*n;i++) dist[i] = 1e18, f[i] = 0;
	dist[st] = 0;
	
	priority_queue<PII, vector<PII>, greater<PII> > que;
	que.push({
    0, st});
	
	while(que.size())
	{
    
		int x = que.top().se; que.pop();
		if(f[x]) continue;
		f[x] = 1;
		
		if(x == en) return dist[x];
		
		for(auto it : e[x])
		{
    
			int tx = it.fi, dis = it.se;
			if(dist[tx] > dist[x] + dis)
				dist[tx] = dist[x] + dis, que.push({
    dist[tx], tx});
		}
	}
	return -1;
}

void init()
{
    
	for(int i=1;i<=n;i++) v[i].clear();
	for(int i=1;i<=2*n;i++) e[i].clear();
	maxdep = 1;
}

signed main(){
    
	T = read();
	while(T--)
	{
    
		n = read();
		
		init();
		
		for(int i=1;i<n;i++)
		{
    
			int x, y, z; 
			x = read(), y = read(), z = read();
			e[x].push_back({
    y, z});
			e[y].push_back({
    x, z});
		}
		
		k = read(), p = read();
		st = read(), en = read();
		
		bfs();
		
		for(int i=1;i<=n;i++)
		{
    
			int tx = i + k;
			if(tx > maxdep) break; //It doesn't matter if it is greater than the maximum depth 
			
			for(int t : v[i]) e[t].push_back({
    n+i, p});
			for(int t : v[tx]) e[n+i].push_back({
    t, 0});
		}
		
		printf("%lld\n", dij());
	}
	
	return 0;
}

---

经验
建立虚点,很妙的做法.

Also see an app：
If there are several starting points,several endpoints,Find the shortest distance from any starting point to any ending point.
At this time, if you do it simply, you will run n 次最短路,But you can create a virtual source point,Connect edges to all origins,权值为 0,Then it only takes one time to run the shortest path from this source.

很妙！