首页 > 其他分享 >CF786B 题解

CF786B 题解

时间:2024-09-11 18:03:21浏览次数:12  
标签:int 题解 线段 dijstra MAXN 建边 CF786B 节点

题意

洛谷题面传送门

现有一个图,有 \(n\) 个节点,从节点 \(s\) 出发,求到 \(n\) 个点每一个点的最短路。

其中,有三种建边方式 :

  • 建一条从 \(u\) 到 \(v\) 的单向边。

  • 从节点 \(v\) 分别向 \([l,r]\) 的每个结点连一条边。

  • 从节点 \([l,r]\) 向节点 \(v\) 连边


芝士

线段树优化 \(dijstra\)


思路

观察数据范围,发现如果全部按照普通 \(dijstra\) 的建图方法来做的话,会TLE

因此,可以发现需要优化建图,而通读了题面,发现恰好是区间的操作使得我们的时间不够用,于是可以想到用线段树优化 \(dijstra\) 。


具体实现

  1. 建树
  • 在使用线段树优化 \(dijstra\) 时,需要两个树,一个是出,一个是入,所以每一条边都应为单向边。

  • 其中每一个树上的每一条边的边权都为 \(0\) 。

  • 应在两棵树上节点序号相同的两个点之间连一条边权为 \(0\) 双向边,因为这两个点本来就是同一个(或是一些)星球。

  • 在我的做法中我将两个线段树都放入了一个数组中,并将 \(K\) (常量,根据数据范围算出)表示为一颗线段树最大的大小,因此,上文中两棵树上相同序号的点在我的写法中分别为 \(i\) 与 \(i+K\) 。

  • 需要在建树时预处理出所有单个星球在线段树上对应的节点编号,并储存下来,这里使用 \(a_i\) 来表示星球 \(i\) 在(编号较小的那颗)线段树上对应的节点编号。对应的,在编号较大的那颗线段树上所对应的编号应为 \(a_i+K\) 。

  1. 建边 (vector好耶)
  • 第一种就是普通的建边,将 \(a_v\) 与 \(a_u\) 连一条单向边。

  • 第二种和第三种就是使用 \(update\) 在线段树上找到可以代表 \([l,r]\) 区间内的所有星球的一些点,并与另一棵树上的代表 \(v\) 的叶子节点建边。

  1. 跑 \(dijstra\) 时
  • 就普通地跑。

tips

  • 注意\(a_i\) 与 \(i\) 的区别

  • 注意区分出树和入树。


代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN=1e5+5;
int n,q,s,K=4e5+5;
int tr[MAXN*8],vis[MAXN*8],a[MAXN*8];
long long d[MAXN*8];
vector<int>vec[MAXN*8],val[MAXN*8];
void add(int u,int v,int d){//建边 
    vec[u].push_back(v);
    val[u].push_back(d);
    return ;
}
void build(int rt,int l,int r){
    if(l==r){
        a[l]=rt;
        add(a[l],a[l]+K,0);
        add(a[l]+K,a[l],0);//同一个星球,建双向边 
        return ;
    }
    int mid=l+r>>1;
    build(rt<<1,l,mid);
    build(rt<<1|1,mid+1,r);
    add(rt,rt<<1,0),add(rt,rt<<1|1,0);//相邻的节点,建单向边(父节点与子节点) 
    add((rt<<1)+K,rt+K,0),add((rt<<1|1)+K,rt+K,0);
}
void update(int rt,int l,int r,int L,int R,int w,int u){//第二和三种建边 
    if(L<=l && R>=r){
        if(u<=K){
            add(rt+K,u,w);
        }
        else{
            add(u,rt,w);
        }
        return ;
    }
    int mid=l+r>>1;
    if(mid>=L){
        update(rt<<1,l,mid,L,R,w,u);
    }
    if(R>mid){
        update(rt<<1|1,mid+1,r,L,R,w,u);
    }
    return ;
}
struct node{
    int v;
    long long d;
	bool operator<(const node &a)const{
		return d>a.d;
	}
};
void dij(){//最最最普通的最短路 
    priority_queue<node>q;
    q.push(node{s,0});
    d[s]=0;
    while(!q.empty()){
        int u=q.top().v;
		long long di=q.top().d;
        q.pop();
        if(vis[u]){
            continue;
        }
        vis[u]=1;
        for(int i=0;i<vec[u].size();i++){
            int v=vec[u][i],dis=val[u][i];
            if(di+dis<d[v]){
                d[v]=di+dis;
                q.push(node{v,d[v]});
            }
        }
    }
}
int main(){
    cin>>n>>q>>s;
    build(1,1,n);
    while(q--){
        int opt;
        cin>>opt;
        if(opt==1){
            int u,v,w;
            cin>>u>>v>>w;
            add(a[u],a[v],w);//注意这里是a[u]和a[v]而非u和v 
        }
        else{
            int u,l,r,w;
            cin>>u>>l>>r>>w;
            update(1,1,n,l,r,w,a[u]+K*(opt==2));
        }
    }
    memset(d,0x3f,sizeof(d));
    s=a[s]+K;
    dij();
    for(int i=1;i<=n;i++){
        if(d[a[i]]==0x3f3f3f3f3f3f3f3f){//注意特判 
            cout<<-1<<" ";
            continue;
        }
        cout<<d[a[i]]<<" ";
    }
}


结语

只是彩笔博主瞎掰扯,他自己都看不懂自己在干什么,欢迎指出博主的问题靴靴qaq。

被数据结构薄纱了

标签:int,题解,线段,dijstra,MAXN,建边,CF786B,节点
From: https://www.cnblogs.com/Le-Louvre/p/18408660

相关文章

  • Power Designer 连接 PostgreSQL 逆向工程生成pd表结构操作步骤以及过程中出现的问题
    、使用PowerDesigner16.5链接pg数据库1.1、启动PD.选择CreateModel…。 1.2、选择Modeltypes/PhysicalDataModelPhysicalDiagram:选择pgsql直接【ok】  1.3、选择connect在工具栏选择Database-Connect…快捷键:ctrl+shift+N.如下图:  1.4、选择配置连接......
  • 【洛谷 P5076】【深基16.例7】普通二叉树(简化版)题解(多重集合+lower_bound+upper_bound
    【深基16.例7】普通二叉树(简化版)题目描述您需要写一种数据结构,来维护一些数(都是以内的数字)的集合,最开始时集合是空的。其中需要提供以下操作,操作次数不超过:查询数的排名(排名定义为比当前数小的数的个数。若有多个相同的数,应输出最小的排名)。查询排名为的数。求的前驱(......
  • P6684 题解
    CF1386CP6684cf上时限\(1\)秒,洛谷\(2\)秒。思路维护是否有奇环可用拓展域并查集。暴力复杂度\(O(mq)\)。发现插入容易删除困难,用不删除的莫队,可撤销并查集,复杂度\(O((n+q)\sqrtm\logn)\)。大概要\(5\)秒左右,只能过洛谷上的前\(5\)个子任务。等价对于每个\(r\)......
  • 单词游戏 题解
    四倍经验51nod2875单词游戏acwing1185.单词游戏洛谷SPOJWORDS1-PlayonWords单词PlayonWords我们可以将每一个字母看成一个节点,这样我们就有了一个包含26个节点的图,对于读入的单词,我们将首字母和尾字母对应的节点之间建有向边(中间的字母没什么用就不管了)。此......
  • 【秋招笔试】9.09阿里国际秋招(已改编)-三语言题解
    ......
  • 【秋招笔试】9.08字节跳动秋招(已改编)-三语言题解
    ......
  • 挑战不可能篇1——洛谷28分钟14道CCF GESP C++ 一级上机题&洛谷14道题题解
    扯谈今天继续挑战不可能:洛谷28分钟14道题这我个人认为不简单,算上编译、提交、命名等杂七杂八的东东之后,只剩下了大约1分钟/题。本次挑战的是CCFGESPC++一级上机题.这竟然能成功!下面附上每一题第一题第二题第三题第四题第五题第六题第七题第八题第九题第十题......
  • [ARC106F] Figures 题解
    生成函数大法好。思路考虑prufer序列。如果\(n\)个点的度数确定,那么生成树个数为:\[\frac{(n-2)!}{\prod(d_i-1)}\]那么在此题中,\(n\)个点的度数确定,那么方案数为:\[\frac{(n-2)!}{\prod(d_i-1)}\prod\frac{a_i!}{(a_i-d_i)!}\]其中,\(\sumd_i=2\timesn-2\)。容易发......
  • CF1672F2 Checker for Array Shuffling 题解
    题目链接点击打开链接题目解法我怎么F1都不会做/llF1:由原始值向最终值连边如果是排列的话,操作次数显然为\(n-\)环数拓展到非排列的情况,即相同数之间的下标可以选择顺序,要求分出来的环数最大直接考虑上面的这东西,让我进入了死胡同。。先给出一个结论:最大环数的最小值是......
  • 【JAVA线上问题解决】JAVA应用程序CPU持续飙高,如何排查问题,如何快速定位问题,解决问题?
    【JAVA线上问题解决】JAVA应用程序CPU持续飙高,如何排查问题,如何快速定位问题,解决问题?场景一、JAVA程序中某个线程占用CPU飙高,问题定位top、jstack命令的使用四步教你快速定位问题代码1.top命令获取异常的java进程PID   top2.查询异常进程中的线程情况,获取异常......