rt:

问题描述

魔法师小g意外闯入一处迷宫，迷宫的道路构成一棵树，经过一条道路需要耗费 $w_i$ 点能量。

在迷宫的入口处，小g捡到了一本传送卷轴。使用该卷轴可以耗费 $p$ 点能量瞬间传送到另一处节点，且可以多次使用，不过需要满足一定的条件。设当前所在节点为 $u$，目的节点为 $v$，必须满足 $|dep_u-dep_v|=k$ 才能进行传送。其中，$dep_u$ 表示以 $1$ 号点作为树根时 $u$ 节点的深度。

该迷宫的起点为 $s$ 终点为 $t$，请你帮忙计算最少需要耗费多少能量才能到达终点。

输入格式

多组数据，第一行输入 $T$，每组数据：

第一行输入 $n$ 。

接下来 $n-1$ 行，每行输入一条双向边 $u_i,v_i,w_i$ 。

然后输入 $k,p$ 。

最后输入 $s,t$ 。

输出格式

输出最少的能量。

样例输入

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

样例输出

12

提示

$1 \le T \le 5$

$2 \le n \le 10^6$

$1 \le u_i,v_i,s,t \le n,u_i \neq v_i,s \neq t$

$1 \le w_i,k \le 10^6$

$0 \le p \le 10^6$

如下代码 WA0 了 （不要管我的码风）

#include <cstring>
#include <iostream>
#include <queue>
using namespace std;
constexpr int N = 2000005, M = 3000005;
int cnt, ev[M], ew[M], nxt[M], lst[N], dep[N];
long long dis[N];
bool vis[N];
inline void add_edge(int u, int v, int w)
{
    ev[++cnt] = v;
    ew[cnt] = w;
    nxt[cnt] = lst[u];
    lst[u] = cnt;
}
void dfs(int u, int fa)
{
    dep[u] = dep[fa] + 1;
    for (int e = lst[u]; e; e = nxt[e]) {
        int v = ev[e];
        if (v == fa)
            continue;
        dfs(v, u);
    }
}
long long dijkstra(int s, int t)
{
    memset(vis, 0, sizeof(vis));
    memset(dis, 0x3f, sizeof(dis));
    struct node {
        int id;
        long long w;
        bool operator<(const node other) const
        {
            return w > other.w;
        }
    };
    priority_queue<node> heap;
    dis[s] = 0;
    heap.push({ s, 0 });
    while (heap.size()) {
        int u = heap.top().id;
        heap.pop();
        if (vis[u])
            continue;
        vis[u] = true;
        if (u == t)
            return dis[t];
        for (int e = lst[u]; e; e = nxt[e]) {
            int v = ev[e], w = ew[e];
            if (vis[v])
                continue;
            if (dis[u] + w < dis[v]) {
                dis[v] = dis[u] + w;
                heap.push({ v, dis[v] });
            }
        }
    }
    return -1;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        memset(lst, 0, sizeof(lst));
        cnt = 0;
        for (int i = 1; i < n; ++i) {
            int u, v, w;
            cin >> u >> v >> w;
            add_edge(u, v, w);
            add_edge(v, u, w);
        }
        dfs(1, 0);
        int maxx = 0;
        for (int i = 1; i <= n; ++i) {
            add_edge(i, n + dep[i], 0);
            add_edge(n + dep[i], i, 0);
            maxx = max(maxx, n + dep[i]);
        }
        int k, p, s, t;
        cin >> k >> p >> s >> t;
        for (int i = n + 1; i <= maxx - k; ++i) {
            add_edge(i, i + k, p);
            add_edge(i + k, i, p);
        }
        cout << dijkstra(s, t) << '\n';
    }
    return 0;
}

请问 dalao 们怎么回事？