2022“杭电杯”中国大学生算法设计超级联赛（5）1003.Slipper dijkstra

题目分析

给定带边权树，经过边需要花费边权代价。定义$de{p}_x$表示节点深度，$|de{p}_u-de{p}_v|=k$时可以直接花费$p$从$u$跳到$v$。求$s$到$t$的最小代价。

首先排除建满边的做法，空间复杂度肯定过不去。

那么考虑跳操作的性质规律：在跑最短路时，对于当前节点$x$，设能够跳到的点集分别为 u p d { } , d n d { } upd\{\}, dnd\{\} upd{},dnd{}，分别满足$|de{p}_{upd}-de{p}_x|=x,|de{p}_{dnd}-de{p}_x|=x$，此时我们会将两个集合入队，这时是通过跳的操作入队。

此后我们会发现：如果通过任意次操作，再次将两个集合入队时，此时的操作一定不是最优的(同一操作执行若干次再次到达当前状态)。那么每个 u p d { } , d n d { } upd\{\}, dnd\{\} upd{},dnd{}集合至多被入队一次，我们在跑$dijkstra$时暴力清空即可。

对于 u p d { } , d n d { } upd\{\}, dnd\{\} upd{},dnd{}，我们可以维护一个表$depg[i]$表示深度为$i$的点集，每次枚举$x$的时候通过$dep[x]-k,dep[x]+k$得到 u p d { } , d n d { } upd\{\}, dnd\{\} upd{},dnd{}即可。

Code

#include 
#pragma gcc optimize("O2")
#pragma g++ optimize("O2")
#define int long long
#define endl '\n'
using namespace std;

const int N = 1e6 + 10, MOD = 1e9 + 7;

struct edge{
    int v, w;
    const bool operator<(const edge &x) const { return w > x.w; }
};

vector<edge> g[N];

int n = 0, k = 0, p = 0, s = 0, t = 0;

vector<int> deg[N];

int dep[N], ind, max_dep;

void dfs1(int u, int fa){
    dep[u] = dep[fa] + 1;
    deg[dep[u]].emplace_back(u);
    max_dep = max(max_dep, dep[u]);
    for(auto &now : g[u]){
        int v = now.v, w = now.w;
        if(v == fa) continue;
        dfs1(v, u);
    }
}

priority_queue<edge> pq;

int dis[N], vis[N];

void dijkstra(){
    while(pq.size()) pq.pop();
    pq.push({s, 0});
    while(pq.size()){
        edge x=pq.top(); pq.pop();
        int u = x.v, w = x.w;
        if(vis[u])continue;
        vis[u] = 1, dis[u] = w;
        for(int i = 0; i < g[u].size(); i++)  pq.push({g[u][i].v, w + g[u][i].w});
        int upd = dep[u] - k, dnd = dep[u] + k;
        if(upd > 0){
            for(int i = 0; i < deg[upd].size(); i++) pq.push({deg[upd][i], w + p});
            deg[upd].clear();
        }
        if(dnd <= max_dep){
            for(int i = 0; i < deg[dnd].size(); i++) pq.push({deg[dnd][i], w + p});
            deg[dnd].clear();
        }
    }
}

inline void solve(){
    cin >> n; max_dep = -1, ind = 0;
    for(int i = 1; i <= n - 1; i++){
        int u, v, w; cin >> u >> v >> w;
        g[u].emplace_back(edge{v, w});
        g[v].emplace_back(edge{u, w});
    }
    cin >> k >> p >> s >> t;
    dfs1(1, 0);
    dijkstra();
    cout << dis[t] << endl;
    //-----------------clear----------------------------//
    for(int i = 1; i <= max_dep + 1; i++) deg[i].clear();
    for(int i = 1; i <= n; i++) g[i].clear();
    for(int i = 1; i <= n; i++) vis[i] = dis[i] = 0;
    //-----------------clear----------------------------//
}   

signed main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout << fixed << setprecision(12);
    int t = 1; cin >> t;
    while(t--) 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
80
81
82
83