专栏文章

题解：P9724 [EC Final 2022] Chase Game

GGYHL
P9724题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mintoac0
此快照首次捕获于
2025/12/02 08:10
3 个月前
此快照最后确认于
2025/12/02 08:10
3 个月前
查看原文
题目描述
Shou 教授被 Pang 教授在一个 m(n−1≤m≤2×105)m(n-1\le m\le2\times10^5) 条边的无向无权简单图上追赶。最初，Shou 教授在顶点 11。他的目的地是顶点 n(2≤n≤105)n(2\le n\le10^5)。Pang 教授在顶点 k(1≤k≤n)k(1\le k\le n)。 每秒钟，Shou 教授可以选择一个相邻的顶点并走向该顶点。然后，Shou 教授会受到 Pang 教授的攻击。此次攻击的伤害等于 d−disd-dis，其中 d(1≤d≤2×105)d(1\le d\le 2\times10^5) 是 Pang 教授的攻击范围，disdis 是图上从 Shou 教授到 Pang 教授的距离（最短路径上的边数）。然而，当 disdis 大于或等于 dd 时，Pang 教授无法造成任何正伤害。在这种情况下，他将会传送到 Shou 教授所在的顶点，然后造成 dd 伤害。（当 disdis 小于 dd 时，Pang 教授将停留在 当前顶点） 请找出 Shou 教授从顶点 11 到顶点 nn 所需的最小伤害总和。Shou 教授将在顶点 nn 处受到最后一次攻击。
如果瞬移了一次，那么以后的伤害都是 d,d−1,…,1,dd,d−1,\dots,1,d，顺移到的都是之前走过的位置，如果距离没变，那么距离终点的最短路也没变，白吃了伤害。 剩下的就是最开始距离小于 dd 的位置，对这些位置跑最短路。之后直接走到终点的最短路，此时已经瞬移了一次了。
代码CPP
#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;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...