跳至内容
CVBB ACM Team
用户工具
注册
登录
站点工具
搜索
工具
显示页面
修订记录
Copy this page
导出 PDF
反向链接
最近更改
媒体管理器
网站地图
注册
登录
>
最近更改
媒体管理器
网站地图
您在这里:
front_page
»
2023-2024
»
teams
»
al_in_and_back_to_whk
»
23-nowcoder-4
»
i
2023-2024:teams:al_in_and_back_to_whk:23-nowcoder-4:i
本页面只读。您可以查看源文件,但不能更改它。如果您觉得这是系统错误,请联系管理员。
==== 题面描述 ==== 一个 $n$ 个点的有向图,给其邻接矩阵,现在可以是一对 $a_{i,j},a_{j,i}$ 均变为 $0$ ,求按顺序走过长度为 $k$ 的点列的最短时间。 $n \le 500, k \le 10^6$ ==== 题解 ==== 考虑先预处理出来点对间的最短路,和相邻点对出现的次数,之后分析一对 $i,j$ 变化后带来的影响。 对于一对相邻点对 $s,t$ ,变化带来的影响是 $c(s,t)*max(0,dis(s,t)-dis(s,i)-dis(j,t),dis(s,t)-dis(s,j)-dis(i,t))$ 。注意到后面两项不可能都大于 $0$ ,所以可以分别和 $0$ 取较大之后再加起来。 然后考虑将 $dis(s,i)$ 对 $i$ 排序,$dis(j,t)$ 对 $j$ 排序,之后枚举 $s,t$ 利用双指针和差分来实现对每对 $(i,j)$ 的答案,之后取最大值即可。
2023-2024/teams/al_in_and_back_to_whk/23-nowcoder-4/i.txt
· 最后更改: 2023/07/29 22:22 由
11231123
页面工具
显示页面
修订记录
反向链接
Copy this page
导出 PDF
回到顶部