音乐播放器
HMF-have much fun Site
 
文章 标签
16
✎首页 ✎首页
☰归档 ☰归档
★标签 ★标签
☎关于 ☎关于
♚推荐 ♚推荐
说说 说说
友人帐 友人帐
Powered by Gridea | Theme: Fog
载入天数...
载入时分秒...
总访问量:  |   访问人数:
Copyright © 2020 备案号: 闽ICP备21335467号
阅
2022-03-29
5 min read
CodeForce 题解

【题解】CF1163F Indecisive Taxi Fee

  热度: loading...

每周文章计划 2021.12 第三周

管理求过

定义：

disidis_i ： 1∼i1 \sim i 的最短路

distidist_i ： n∼in \sim i 的最短路

u,v,wu,v,w ：边的两个端点以及边权

preupre_u ：uu 在最短路上的前驱点

preedgeupreedge_u ：uu 在最短路上的前驱边

lu,rul_u,r_u ：经过 uu 点的最短路与原最短路重合的前缀长度，经过 uu 点的最短路与原最短路重合的后缀长度。

题目大意

给你一个 nn 个点，mm 条边的无向图，每条边连接点 uu、vv，并且有个长度 ww 。

有qq次询问，每次询问给你一对 tt、xx, 表示仅当前询问下，将 tt 这条边的长度修改为 xx，请你输出当前 11 到 nn 的最短路长度。

数据范围

2≤n≤2×1052 \le n \le 2\times10^5

1≤m,q≤2×1051 \le m, q \le 2\times10^5

1≤wi,xi≤1091 \le w_i,x_i \le 10^9

首先由于这是最短路问题，我们先求出 1∼n1 \sim n 的最短路。

然后考虑修改，我们将修改分为四种：

1. 修改在最短路上，边权变小

这种是最好解决的，最短路上的边权变小肯定还是最短路，所以直接输出新的最短路 (disn−wlast+wnew)(dis_n-w_{last}+w_{new}) 即可。

2. 修改不在最短路上，边权变大

这种也好解决，不在最短路上的边的边权变大，最短路肯定还是原来的最短路，输出 disndis_n 即可。

3.修改不在最短路上，边权变小

这个需要稍微想一下，我们可以从 n∼1n \sim 1 再做一遍最短路，然后我们可以用 disu+distv+wnewdis_u+dist_v+w_{new} 和 disv+distu+wnewdis_v+dist_u+w_{new} 来更新答案，这两个中一定有一个是经过 {u,v}\{u,v\} 边的新最短路

4.修改在最短路上，边权变大

这个就是最难想的情况了，这样修改原来的最短路有可能不是最短路，但如果用最短路之外的边修改又不知道用哪条边修改。

当然是丢回去重新跑一遍最短路啊

为了解决这个问题，我们先给出一个结论:

从 1∼n1 \sim n ，经过一条边的最短路径，肯定有一段前缀以及一段后缀和最短路重合

换而言之，就是与最短路不重合的部分最多只有一段，且是连续的。

证明： 如果有多于一段与原最短路不重合，那么这些段中必然只有一段包含 {u,v}\{u,v\} ，其他段改成原最短路上的路径就会使总路程更小，则假设不成立

那么得知了这个结论后，我们可以知道经过 uu 点的最短路，就是不经过第 [lu+1,ru−1][l_u+1,r_u-1] 的最短路，换算到边 {u,v}\{u,v\} 上，就是不经过边 [lu+1,rv−1][l_u+1,r_v-1] 和 [lv+1,ru−1][l_v+1,r_u-1] 的边

看到区间操作，第一反应必然是用线段树 不会是平衡树吧 ，因此我们可以写一颗非常短的维护最小值的线段树，然后维护不经过最短路上每条边时的最短路，在讯问时查询不经过边 {u,v}\{u,v\} 的最短路是否比 disn−wlast+wnewdis_n-w_{last}+w_{new} 短即可。

具体实现

首先是记下最短路，我们从 nn 跳 prepre ,一直跳到 11 ，记录下 preedgepreedge 即可。

对于最短路上的每个点，lul_u 为最短路上链接到自己的边，rur_u 为最短路上自己延伸出去的边。

然后做两遍 Dij ，一遍从 1∼n1 \sim n，一遍从 n∼1n \sim 1，lul_u 和 rur_u 分别从第一遍和第二遍的前驱继承即可。

CF时限卡得紧，记得加快读。

至此本道题完全做完。

赏
  • 文章作者：Linky
  • 原文链接：https://lookcatbox.github.io/post/ti-jie-cf1163f-indecisive-taxi-fee/
  • 版权声明：本博客所有文章除特别声明外，均采用BY-NC-SA 许可协议。转载请注明出处！