自动搬运

查看原文

来自洛谷，原作者为

	FFTotoro 龙猫

搬运于2025-08-24 22:51:11，当前版本为作者最后更新于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;
}