社区讨论
求hack/证明
CF1163FIndecisive Taxi Fee参与者 6已保存回复 15
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 15 条
- 当前快照
- 1 份
- 快照标识符
- @m4lf6isn
- 此快照首次捕获于
- 2024/12/12 22:33 去年
- 此快照最后确认于
- 2025/11/04 23:22 4 个月前
CF过了
就是说先正着求一边，倒着求一边最短路，然后考虑检出正着的最短路径树，只需考虑边在 1~n 的路径上放大的时候，这时就是删边最短路。
然后对于每一条非树边，假设链接 u v，如下图
这样将 lca(u,n)到 lca(u,n,v) 的路径上的边，把他删掉后可以通过 dis[1->v]+w+dis[u->n] 的贡献答案，然后取min即可。
这样思路对吗/kel
就是说先正着求一边，倒着求一边最短路，然后考虑检出正着的最短路径树，只需考虑边在 1~n 的路径上放大的时候，这时就是删边最短路。
然后对于每一条非树边，假设链接 u v，如下图
这样将 lca(u,n)到 lca(u,n,v) 的路径上的边，把他删掉后可以通过 dis[1->v]+w+dis[u->n] 的贡献答案，然后取min即可。
这样思路对吗/kel
回复
共 15 条回复，欢迎继续交流。
正在加载回复...