Life is a Game 题解(启发式合并)

题目链接

题目思路

查询和修改都离线操作

然后查询使用优先队列进行启发式合并即可

代码

#include
#define fi first
#define se second
#define debug cout<<"I AM HERE"<b.k;
    }
};
priority_queue pq[maxn];
signed main(){
    scanf("%d%d%d",&n,&m,&q);
    for(int i=1;i<=n;i++){
        scanf("%lld",&a[i]);
        fa[i]=i;
    }
    for(int i=1;i<=m;i++){
        scanf("%d%d%d",&e[i].u,&e[i].v,&e[i].w);
    }
    sort(e+1,e+1+m,cmp);
    for(int i=1,x,k;i<=q;i++){
        scanf("%d%d",&x,&k);
        pq[x].push({k,i});
    }
    for(int i=1;i<=m;i++){
        int u=findd(e[i].u);
        int v=findd(e[i].v);
        if(u==v) continue;
        while(!pq[u].empty()&&pq[u].top().k+a[u]