Warning: session_start(): open(/tmp/sess_3485684a036f9ccf3f5a28aeefc3fb0b, O_RDWR) failed: No space left on device (28) in /data/wiki/inc/init.php on line 239

Warning: session_start(): Failed to read session data: files (path: ) in /data/wiki/inc/init.php on line 239

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/auth.php on line 430

Writing /data/wiki/data/cache/0/0a1fb0ef465f43d40a68985f0133c2ba.captchaip failed

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/inc/actions.php on line 38

Warning: Cannot modify header information - headers already sent by (output started at /data/wiki/inc/init.php:239) in /data/wiki/lib/tpl/dokuwiki/main.php on line 12
2020-2021:teams:legal_string:jxm2001:数据结构优化建图 [CVBB ACM Team]

2020-2021:teams:legal_string:jxm2001:数据结构优化建图

这是本文档旧的修订版！

目录

数据结构优化建图
- 算法例题
  - 例题一
    - 题意
    - 题解

数据结构优化建图

算法例题

例题一

题意

$n$ 个点的有向图。给定 $3$ 中连边方式，分别为：

$u$ 向 $v$ 连一条边权为 $w$ 的边
$u$ 向 $[l,r]$ 每个节点连一条边权 $w$ 的边
$[l,r]$ 向 $u$ 每个节点连一条边权 $w$ 的边

给定源点 $s$，询问单点源最短路。

题解

考虑建两棵线段树，每棵线段树均维护区间 $[1,n]$。第一棵线段树由根节点

查看代码

查看代码

2020-2021/teams/legal_string/jxm2001/数据结构优化建图.1613007027.txt.gz · 最后更改: 2021/02/11 09:30 由 jxm2001