20241030 训练记录

[TJOI2012] 桥

删边最短路模板。

只需求出对于每条边，不经过这条边的最短路就做完了。

考虑不在原 \(1\) 到 \(n\) 最短路上的边，它们的答案就为原本的最短路。

对于原本就在最短路上的边，既然删掉了这条边，那么新的最短路一定会经过另外一条边，设这条边为 \((u,v,w)\)，\(dis(u,v)\) 表示 \(u\) 到 \(v\) 的最短路。那么经过这条边的最短路就为：

考虑使用这个值去更新在最短路上的边的答案。考虑这条边能更新哪些边的答案。

难点：发现性质。在新的最短路中，考虑把经过的边拉出来变成一个序列，与原最短路的序列进行比较，发现两个序列一定有一段前缀和一段后缀是相同的。也就是说，在原本最短路经过的边中，只有中间一段连续的边在新最短路中没有出现过。那么如果能找出这个区间，我们就能使用线段树区间取 \(\max\)，单点查询解决问题。

如何找出这个区间呢？考虑建出最短路生成树。具体地说，记录每个点的最短路从哪里转移过来，把那个点作为这个点的父亲，得到一颗树。这样，只要求出两个点在这颗树上的 LCA，就能知道最长的公共前、后缀，从而知道一条边能更新哪个区间，这题就做完了。

找区间的部分似乎可以通过 bfs 在线性时间内求出所有区间，但是我不会。

注意点：

1.需要建出以 \(1\) 为根和以 \(n\) 为根的两颗生成树，需要保证两棵树中 \(1\) 到 \(n\) 的最短路是同一条路径。否则最短路不唯一时可能会出现问题。

2.需要特判无论如何删边最短路都不变的情况，不知道为什么。

Indecisive Taxi Fee

考虑一个分类讨论：

1.当修改的边不在原最短路上，且边权增大时，容易发现答案为原最短路。

2.当修改的边不在原最短路上，且边权减小时，如果答案会更新，新答案一定会经过这条边，那么与原最短路取个 \(\min\) 即可。

3.当修改的边在原最短路上，且边权减小时，容易发现最短的路径不变，直接将原最短路减去边权变化量即可。

4.当修改的边在原最短路上，且边权增大时，这时新最短路有两种情况：经过或不经过这条边。经过这条边的最短路就是原最短路加上边权变化量，不经过的就是上一题的删边最短路模板，直接套用即可。

于是这题就做完了。