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

题目分析

给定带边权树，经过边需要花费边权代价。定义 d e p x dep_x depx​表示节点深度， ∣ d e p u − d e p v ∣ = k |dep_u - dep_v| = k ∣depu​−depv​∣=k时可以直接花费 p p p从 u u u跳到 v v v。求 s s s到 t t t的最小代价。

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

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

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

对于 u p d { } , d n d { } upd\{\}, dnd\{\} upd{},dnd{}，我们可以维护一个表 d e p g [ i ] depg[i] depg[i]表示深度为 i i i的点集，每次枚举 x x x的时候通过 d e p [ x ] − k , d e p [ x ] + k dep[x] - k, dep[x] + k 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 x.w; }
};

vector g[N];

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

vector 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 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  0){
            for(int i = 0; i  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