P9724 [EC Final 2022] Chase Game
wangboyue_740325
·
2024-08-14 16:09:29
·
题解
题意
一张简单无向无权图上有 2 个人 A 和 B，A 要从点 1 走到点 n ，B 最开始在点 k 。当 A 移动时：
若 A 与 B 的距离超过 d ，则 B 传送到 A 并对 A 造成 d 的伤害；
否则，定义 AB 间距离为 dis ，B 对 A 造成 d-dis 的伤害。
最小化 A 受到的伤害，输出。
思路
明显地，当 A 与点 k 的距离大于 d 时，A 直接走最短路到点 n 最优。dk_i 表示点 k 到点 i 的最短路长度，dn_i 表示点 n 到点 i 的最短路长度，de_i 表示 A 从点 1 到点 i 收到的伤害的最小值，ans 表示 A 走到点 n 受到的最小伤害。
$de$ 和 $ans$ 的求取较为复杂。当 Dijkstra 枚举到 $cur$，下一个点为 $nxt$ 时有 $2$ 种情况：
1. 若 $dk_{nxt}\ge d$，直接更新答案；
2. 若 $dk_{nxt}<d$，$de_{nxt}\gets de_x+d-dk_{nxt}$。
详见代码。
# 代码
```cpp
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=1e5+5;
int n,m,s,dis[N],de[N],ans=1e18,dn[N],dk[N],k,d;
bool vis[N];
vector<int> nbr[N];
int get(int l,int r){
if(l>r){
return 0;
}
return (l+r)*(r-l+1)/2;
}
int getsum(int x){
return x/d*get(1,d)+get(d+1-x%d,d);
}
struct node{
int y,w;
bool operator<(const node &o)const{
return w>o.w;
}
};
void dij(int s,bool f,int ds[]){
for(int i=0;i<=n;i++){
ds[i]=1e18;
vis[i]=false;
}
priority_queue<node> q;
ds[s]=0;
q.push({s,0});
while(!q.empty()){
node cur=q.top();
q.pop();
int x=cur.y,w=cur.w;
if(vis[x]){
continue;
}
vis[x]=true;
for(int nxt:nbr[x]){
if(!f){
if(ds[x]+1<ds[nxt]){
ds[nxt]=ds[x]+1;
q.push({nxt,ds[nxt]});
}
}
else{
if(dk[nxt]>=d){
ans=min(ans,de[x]+getsum(dn[nxt]+1));
// cerr<<"Updated ans! "<<ans<<endl;
}
else if(de[x]+d-dk[nxt]<de[nxt]){
de[nxt]=de[x]+d-dk[nxt];
// cerr<<"Relax "<<nxt<<"<-"<<de[nxt]<<endl;
q.push({nxt,de[nxt]});
}
}
}
}
return;
}
signed main(){
cin>>n>>m>>k>>d;
for(int i=1;i<=m;i++){
int a,b;
cin>>a>>b;
nbr[a].push_back(b);
nbr[b].push_back(a);
}
dij(k,false,dk);
dij(n,false,dn);
dij(1,true,de);
cout<<min(de[n],ans);
return 0;
}
```