[EC Final 2022] Chase Game 题解

FFTotoro · 2023-11-19 12:09:40 · 题解

考虑 Pang 教授要怎么追 Shou 教授。一开始如果 Shou 教授一直待在 Pang 教授的攻击范围内那么 Pang 教授就不会动，一旦出了攻击范围 Pang 教授肯定直接就追，具体地，每隔 d 步一个周期，攻击分别为 d,d-1,\ldots 2,1，直到 Shou 教授到达 n 被进行完最后一轮攻击。所以一旦出了范围 Shou 教授肯定就直接沿最短路往 n 走。

于是我们可以用 Dijkstra 算法解题。令 d_{u,v} 为 u 到 v 的最短距离，l_u 为当前到 u 受到的最小伤害。假设现在到了 u，那么走到另一个点 v（u,v 没有出攻击范围）的代价就是 l_u+d-d_{k,v}。如果 v 出了攻击范围，那么就是 l_u 加上从 v 到 n 一路过去 Pang 教授一路追的伤害，可以简单地推式子实现。

注意预处理一下 k 与 n 到每个点的距离，可以使用 01bfs 实现。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
typedef pair<int,int> pii;
main(){
  ios::sync_with_stdio(false);
  int n,m,k,d,c=1e16; cin>>n>>m>>k>>d;
  vector<vector<int> > g(n);
  for(int i=1;i<=m;i++){
    int u,v; cin>>u>>v;
    g[--u].emplace_back(--v);
    g[v].emplace_back(u);
  }
  auto bfs=[&](int u){
    queue<int> q; q.emplace(u);
    vector<int> d(n);
    vector<bool> b(n); b[u]=true;
    while(!q.empty()){
      int u=q.front(); q.pop();
      for(int i:g[u])
        if(!b[i])b[i]=true,d[i]=d[u]+1,q.emplace(i);
    }
    return d;
  }; // 预处理最短距离
  auto s=[](int l,int r){
    return max(0ll,r*(r+1)-l*(l-1)>>1);
  }; // 求 l 到 r 的和
  auto f=[&](int x){
    return x/d*s(1,d)+s(d-x%d+1,d);
  }; // 求一路追过去，总共走了 x 个点的伤害
  vector<int> dk=bfs(k-1),dn=bfs(n-1),l(n,1e16);
  vector<bool> b(n);
  priority_queue<pii,vector<pii>,greater<> > q;
  q.emplace(l[0]=0,0);
  while(!q.empty()){
    int u=q.top().second; q.pop();
    if(b[u])continue; b[u]=true; // 打标记
    for(int i:g[u])
      if(dk[i]>=d)c=min(c,l[u]+f(dn[i]+1)); // 注意要 +1，是因为走到 i 这个点也进去
      else if(l[u]+d-dk[i]<l[i])q.emplace(l[i]=l[u]+d-dk[i],i); // 更新最短路
  } // 使用堆优化 Dijkstra
  cout<<min(c,l[n-1])<<endl; // 也有可能都不出范围
  return 0;
}