主页
搜索
最近更新
数据统计
申请密钥
批量保存
开发版网站（新前端）
系统公告
1
/
1
请查看完所有公告
题解：CF208C Police Station
最后更新于 2025-08-28 08:54:51
作者
2huk
分类
题解
题解
CF208C
复制 Markdown
查看原文
转到新前端
删除文章
更新内容
不妨枚举警察局放在哪。设为 $u$。考虑求解”所有最短路中经过的安全边个数”。 不妨枚举这条安全边 $(u, v)$，然后计算有多少条最短路经过它。对于每个 $v$ 都算一遍然后加和即为答案。 首先，如果 $dis(1,u)+1+dis(v,n)\ne dis(1,n)$ 则无解。这里 $dis(i, j)$ 表示 $i \rightsquigarrow j$ 的最短路长度。 然后做最短路计数。答案为 $cnt(1,u) \times cnt(v,n)$，其中 $cnt(i, j)$ 表示 $i \rightsquigarrow j$ 的最短路条数。 最短路计数见 [P1144](https://www.luogu.com.cn/problem/P1144)。 $cnt(i, j)$ 是否会爆掉 `long long`？不会的。一个最短路最多的例子是这样的：  （虽然题目保证了没有重边，但是没有重边的最短路条数一定比上面这个少。） 此时最短路条数是 $2^{n/2}=2^{50}$。`long long` 存储是没有问题的。 代码：<https://codeforces.com/contest/208/submission/289875013>
正在渲染内容...
点赞
0
收藏
0
