【21 ZR联赛集训 day10】身经百战
显然每个怪物是独立的。
我们考虑对操作建带权边,答案就是求最短路。
但是点数太多,于是我们可以对怪物血量和所有 \(a_i,b_i\) 离散化一下,因为我们只需要考虑这些点,注意 \(1\) 也要离散化,因为我们需要考虑 \(1\)。
一个小优化,如果 \(a_i>b_i\) 且 \(c_i\ge a_i-b_i\) 这条 \((a_i,b_i,c_i)\) 的边没必要加,因为直接操作一一个一个减不会更差。此外自环(\(a_i=b_i\))也是没必要的,重边取最小那条(不过太麻烦了,没必要)。
我们从 \(1\) 开始沿逆向边做最短路,时间复杂度 \(O(m\log m)\)。
Code
#include<bits/stdc++.h>
#define pf printf
#define sf scanf
#define rep(x,y,z) for(int x=y;x<=z;x++)
#define isdigit(x) (x>='0'&&x<='9')
//#define int ll
using namespace std;
typedef long long ll;
const int N=1e6+7,M=1e5+5;
template <typename T>
void read(T &sum){
sum=0;
T fl=1;
char ch=getchar();
for(;!isdigit(ch);ch=getchar()) (ch=='-')&&(fl=-1);
for(;isdigit(ch);ch=getchar()) sum=(sum<<3)+(sum<<1)+ch-'0';
sum=sum*fl;
}
template <typename T>
void write(T x){
static int st[36];
int top=0;
if(x<0) putchar('-'),x=-x;
do{
st[top++]=x%10,x/=10;
}while(x);
while(top) putchar(st[--top]+'0');
}
template <typename T>
void write(T x,char ch){
write(x);
putchar(ch);
}
int head[N<<1],cnt;
struct edge{
int to,val,ne;
}e[N<<2];
void addedge(int u,int v,int w){
swap(u,v);
// pf("(%d %d %d)\n",u,v,w);
e[++cnt]={v,w,head[u]};head[u]=cnt;
}
int n,m;
int v[N];
int a[M],b[M],c[M];
int vec[N<<1];
int len;
int ans[N];
int dis[N<<1],vi[N<<1];
struct qst{
int x,d;
bool operator <(const qst b)const{
return (d!=b.d?d>b.d:x>b.x);
}
};
void getdis(int rt){
memset(vi,0,sizeof(vi));
priority_queue<qst> que;
dis[rt]=0;
que.push({rt,0});
while(!que.empty()){
qst k=que.top();
que.pop();
int u=k.x,d=k.d;
if(vi[u]) continue;
vi[u]=1;
// pf("u: %d\n",u);
for(int i=head[u];i;i=e[i].ne){
int v=e[i].to,w=e[i].val;
if(d+w<dis[v]){
dis[v]=d+w;
// pf("v: %d,%d\n",v,dis[v]);
que.push({v,dis[v]});
}
}
}
}
ll sum;
signed main(){
read(n),read(m);
rep(i,1,n){
read(v[i]);
vec[++vec[0]]=v[i];
}
rep(i,1,m){
read(a[i]),read(b[i]),read(c[i]);
vec[++vec[0]]=a[i],vec[++vec[0]]=b[i];
}
vec[++vec[0]]=1;
sort(vec+1,vec+vec[0]+1);
len=unique(vec+1,vec+vec[0]+1)-vec-1;
rep(i,2,len) {
// pf("%d ",vec[i]);
addedge(i,i-1,vec[i]-vec[i-1]);
}
// pf("\n");
rep(i,1,n){
int x=lower_bound(vec+1,vec+len+1,v[i])-vec;
ans[i]=x;
}
rep(i,1,m){
if((c[i]>=a[i]-b[i]&&a[i]>b[i])||a[i]==b[i]) continue;
int u=lower_bound(vec+1,vec+len+1,a[i])-vec,
v=lower_bound(vec+1,vec+len+1,b[i])-vec;
addedge(u,v,c[i]);
}
memset(dis,0x7f,sizeof(dis));
getdis(lower_bound(vec+1,vec+len+1,1)-vec);
rep(i,1,n){
// pf("%d\n",dis[ans[i]]);
sum+=dis[ans[i]];
}
write(sum);
}
没有回复内容