题解：P9724 [EC Final 2022] Chase Game

· · 题解

:::info[题目描述]{close} Shou 教授被 Pang 教授在一个 m(n-1\le m\le2\times10^5) 条边的无向无权简单图上追赶。最初，Shou 教授在顶点 1。他的目的地是顶点 n(2\le n\le10^5)。Pang 教授在顶点 k(1\le k\le n)。 每秒钟，Shou 教授可以选择一个相邻的顶点并走向该顶点。然后，Shou 教授会受到 Pang 教授的攻击。此次攻击的伤害等于 d-dis，其中 d(1\le d\le 2\times10^5) 是 Pang 教授的攻击范围，dis 是图上从 Shou 教授到 Pang 教授的距离（最短路径上的边数）。然而，当 dis 大于或等于 d 时，Pang 教授无法造成任何正伤害。在这种情况下，他将会传送到 Shou 教授所在的顶点，然后造成 d 伤害。（当 dis 小于 d 时，Pang 教授将停留在 当前顶点） 请找出 Shou 教授从顶点 1 到顶点 n 所需的最小伤害总和。Shou 教授将在顶点 n 处受到最后一次攻击。 :::

如果瞬移了一次，那么以后的伤害都是 d,d−1,\dots,1,d，顺移到的都是之前走过的位置，如果距离没变，那么距离终点的最短路也没变，白吃了伤害。 剩下的就是最开始距离小于 d 的位置，对这些位置跑最短路。之后直接走到终点的最短路，此时已经瞬移了一次了。

:::info[代码]{close}

#include<bits/stdc++.h>
#define int long long
#define pi pair<int, int>
#define xx first
#define yy second

using namespace std;
const int N = 1e5 + 10;
int n, m, k, d, dk[N], dn[N], ans = LLONG_MAX, dis[N];
vector<int> G[N];
bool vis[N];

int get(int l, int r){
    return (l + r) * (r - l + 1) / 2;
}

int gs(int x){
    return x / d * get(1, d) + get(d + 1 - x % d, d);
}

void bfs(int x, int *dis){
    queue<int> q;
    q.push(x);
    memset(vis, 0, sizeof vis);
    vis[x] = 1;
    while(!q.empty()){
        int u = q.front();
        q.pop();
        for(int v : G[u]){
            if(!vis[v]){
                vis[v] = 1;
                q.push(v);
                dis[v] = dis[u] + 1;
            }
        }
    }
    return ;
}

void dij(int x){
    priority_queue<pi, vector<pi>, greater<pi>> q;
    memset(dis, 0x3f, sizeof dis);
    memset(vis, 0, sizeof vis);
    dis[x] = 0;
    q.push({0, x});
    while(!q.empty()){
        int u = q.top().yy;
        q.pop();
        if(vis[u])continue;
        vis[u] = 1;
        for(int v : G[u]){
            if(dk[v] >= d)ans = min(ans, dis[u] + gs(dn[v] + 1));
            else if(dis[u] + d - dk[v] < dis[v]){
                dis[v] = dis[u] + d - dk[v];
                q.push({dis[v], v});
            }
        }
    }
    return ;
}

inline int read(){
    int x;
    cin>>x;
    return x;
}

signed main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    n = read(), m = read(), k = read(), d = read();
    for(int i = 1; i <= m; i ++){
        int u = read(), v = read();
        G[u].push_back(v);
        G[v].push_back(u);
    }
    bfs(k, dk), bfs(n, dn), dij(1);
    cout << min(ans, dis[n]);
    return 0;
}

:::