Hdu 2022多校训练（5） Slipper

题意：
给定一个树，问两点间的最短路径，如果深度差距为K那么可以用一定花费去跳越。
题解：
在每一层中都连接两个虚拟点，一个作为出边，一个作为入边，边权为0，作为中转点，然后深度差距为K的虚拟点之间相互连接边权为P，需要注意上层的出点与下层入点向连，下层的出点与上层的入点相连。容易错的地方是连一个点作为虚拟点，连接无向边，然后虚拟点之间连接无向边。这样错的地方是同一深度的节点最短路径会为0.图建完之后跑一遍最短路径即可。

#include 
#include 
#include 
#include 
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;//求每个节点的深度
    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 为入点
        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);//第i层出点 连下(i+k)层的入点
        addEdge(n + 2 * (dep[i] + k) + 2, n + 2 * dep[i] + 1);//第i+k层的出点，连第i层的入点
    }
    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;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79