CF2194E The Turtle Strikes Back

考虑先处理出起点到某个位置的最大路径，某个位置到终点的最大路径。那么我们枚举翻转的位置。那么对于经过这个位置的最短路就是 \(f_{i,j}+g_{i,j}-3a_{i,j}\)。

考虑如果不经过这个点。我们发现对于这个点，所有路径一定会经过和它同步到达的点中的一个，且不会再经过这个点。那么我们考虑经过这个点的最优路径是原先那条线中的最大值还是比最大值小，如果是最大值那么我们维护一下每一条线的非严格次大路径，否则可以直接经过这条线的最大路径。