主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：P10206 [JOI 2024 Final] 建设工程 2
最后更新于 2025-08-28 09:09:12
作者
2huk
分类
题解
题解
P10206
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
### 题意 给定一张无向图。求有多少 $u < v$ 满足在 $u, v$ 间连一条边权为 $l$ 的边后，$s \rightsquigarrow t$ 的最短路 $\le k$。 ### 做法 首先判掉最开始 $s \rightsquigarrow t$ 的最短路已经 $\le k$ 的情况。答案是 $\binom n2$。 否则，若原来最短路 $> k$，但加上 $(u, v)$ 这条边后最短路 $\le k$ 了，那么这条最短路已经经过 $(u, v)$ 这条边。 那么 $s \rightsquigarrow t = s \rightsquigarrow u + (u,v) + v \rightsquigarrow t$，其中前一部分和后一部分都可以预处理。于是问题转化成了： - 求有多少 $u < v$ 满足 $a_u+l+b_v\le k$ 或 $a_v+l+b_u\le k$。 显然可以移项。显然可以固定 $u$ 并二分查找 $v$。显然这个问题是极易的。
正在渲染内容...
点赞
1
收藏
0
