题目： 给个点。个操作。：和建权值的有向边；：和建权值的有向边； ：和建权值的有向边； 问从点到其他点的最短路。无法到达输出。 做法： 直接建图时间、空间复杂度都太大了。我们需要用线段树维护区间建图。开两棵线段树，自底向上建零边，自顶向下建零边。如下图：当我们处理这种情况时，只需用和线段树中的某些
展开全文
Legacy 线段树优化建边，开两颗线段树：对于线段树1，自顶向下连边。对于线段树2，自底向上连边。然后对于op1我们直接连边即可。对于op2（u -> [l, r] cost = w），这个操作在线段树1上完成即可。对于op3（[l, r] -> v cost = w），这个操作在线段
展开全文
CF786B 题意： 一张图上有 n 个点，现在做 m 次操作，操作总共有 3 种： 1 a b c： 从 a 到 b 连一条权值为 c 的单向边。(t=1) 2 a b c d：从 a 到 [b, c]中的每个点都连一条权值为 d 的单向边。(t=2) 3 a b c d：从 [b, c]中的每
展开全文
挺好的一个题，线段树建图+拆点+最短路。 这个题一眼看上去感觉不就是对于每个条件，对于区间[l,r]的所有点都连上一条边，完了在跑个最短路就完事儿了。 但是看见数据范围的时候就傻眼了，因为最坏情况每一次会有O(n)个点相关，因此，边的数目都会最坏达到O(N*N)无法接受。 那么，对于1e5左右的数据
展开全文
裸的线段树优化连边,怎么来理解?? 比如,怎么让一个点向一个区间连边?? 这个时候新建一颗线段树,线段树上的点都是虚点 当点连向区间时 就把点连向线段树上完全覆盖的节点 然后线段树上,父节点向儿子连费用零的边,叶子节点向对应的实点连边 这样一来,就可以经过线段树的周转以费用零的代价来到另一个实点.
展开全文
前排参考lifehappy大佬题解 问题描述 给出你n个点构成的一个有向图，并且存在 m 个边的关系，并且询问从起点 s 去往各个点的最短路长度？问题规模：这m个关系中，操作1，直接u连向v一条边权是w的有向边。操作2，使u连向v，但是这个v是在一个区间中 [l, r]中全部的点，边权等于w操作3，
展开全文
-
扫描二维码，关注牛客
- 意见反馈
-
下载牛客APP，随时随地刷题
- 牛客竞赛，专业的竞技算法训练平台
-
扫描二维码，进入QQ群
扫码关注“比赛自动姬”
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备 11010502036488号
