Hdu 2022 Multi-School Training (5) Slipper

题意：
给定一个树,Ask the shortest path between two points,If the depth of the gap asKYou can use a certain cost to jump.
题解：
In each layer are connected two virtual point,As a side,A as the edge,边权为0,作为中转点,And then deep gap forKBetween virtual connection edge right for each otherP,Need to pay attention to the top of the point and the lower entry point to the,The lower the points connected with the upper into the point.Easy wrong place is even a point as a virtual point,Connected undirected edge,And then connected undirected edge between virtual points.Such wrong place is the same depth of nodes shortest paths for0.Figure can be run again when it is completed the shortest path.

#include <algorithm>
#include <cstdio>
#include <cstring>
#include <queue>
using namespace std;
using ll = long long;
const int maxn = 1e6 + 5;
int e[maxn << 3][3], head[maxn << 2], tot = -1;
int dep[maxn << 2], maxdep = 0, n = 0, k = 0, p = 0, s = 0, t = 0;
void addEdge(int u, int v, int w) {
    
    e[++tot][0] = v;
    e[tot][1] = head[u];
    e[tot][2] = w;
    head[u] = tot;
}
void dfs(int u, int fa) {
    
    dep[u] = dep[fa] + 1;//O the depth of each node
    maxdep = max(maxdep, dep[u]);
    for (int i = head[u]; ~i; i = e[i][1]) {
    
        if (e[i][0] == fa)
            continue;
        dfs(e[i][0], u);
    }
}
ll dis[maxn << 2];
bool vis[maxn << 2];
void dijkstra() {
    
    memset(dis, 0x3f, sizeof(dis));
    memset(vis, false, sizeof(vis));
    dis[s] = 0;
    priority_queue<pair<ll, int>> pq;
    pq.emplace(0, s);
    while (!pq.empty()) {
    
        int u = pq.top().second;
        pq.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        for (int i = head[u]; ~i; i = e[i][1]) {
    
            int v = e[i][0], w = e[i][2];
            if (dis[v] > dis[u] + w) {
    
                dis[v] = dis[u] + w;
                pq.emplace(-dis[v], v);
            }
        }
    }
}
void solve() {
    
    memset(head, -1, sizeof(head));
    tot = -1, maxdep = 0;
    scanf("%d", &n);
    int u = 0, v = 0, w = 0;
    for (int i = 1; i <= n - 1; ++i) {
    
        scanf("%d %d %d", &u, &v, &w);
        addEdge(u, v, w), addEdge(v, u, w);
    }
    dep[0] = -1;
    dfs(1, 0);
    scanf("%d %d", &k, &p);
    for (int i = 1; i <= n; ++i) {
    
        addEdge(n + 2 * dep[i] + 1, i);//规定n+2*dep[i]+1 To the point
        addEdge(i, n + 2 * dep[i] + 2);//n+2*dep[i]+2为出点
    }
    for (int i = 1; i <= n; i++)
    {
    
        addEdge(n + 2 * dep[i] + 2, n + 2 * (dep[i] + k) + 1);//第iThere are some 连下(i+k)Layer into the point
        addEdge(n + 2 * (dep[i] + k) + 2, n + 2 * dep[i] + 1);//第i+kLayer of something,连第iLayer into the point
    }
    scanf("%d %d", &s, &t);
    dijkstra();
    printf("%lld\n", dis[t]);
}

int main() {
    
    int T = 0;
    scanf("%d", &T);
    for (int cas = 1; cas <= T; ++cas)   solve();
    return 0;
}