[P6880 JOI 2020 Final] オリンピックバス - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
两条前置知识：
- 在图 \(G\) 上构造根为 \(x\) 的最短路树 \(T\)，我们删除任意一条不在 \(T\) 上的边 \(e\)，\(x\) 到任意一个节点 \(u\) 的距离 \(d(x, u)\) 均不会发生变化。
- 有向图上 \(d(i, x)\) 的求法，其中 \(x\) 为定点。实际上就是构造 \(G\) 的反图，在反图上跑 \(x\) 为源点的 dijkstra 即可。
这个题我的第一反应是分层图，把原图分为两层然后两层之间用反边单向导通。也就是这个题。
但是这样可以被 hack，看下面这个例子：
唯一一种可行的走法是：翻转 \(4 \to 3\) 这条边，然后 \(1 \to 2 \to 3 \to 4 \to 5 \to 6 \to 9 \to 8 \to 3 \to 4 \to 7 \to 1\)。
可以看到 \(3 \to 4\) 我们走了两次，分层图不能很好的处理一条道路被翻转然后被走两次（注意到我上面给的另一道题，那个题本身就不允许在一条道路上反走两次，但这个题可以）。
思考发现好像怎么改分层图的模型也不能处理这个问题。先扔在一边。
注意到原题的一个条件：\(n \le 200\)。也就是这个图是稠密的？不过还有一个更强的性质，某棵最短路树最多只有可能有 \(199\) 条边，剩余的边我们都可以利用前置知识第一条加速计算。
实际上翻转一条边 \(e\) 可以看做删除 \(e\) 然后再添加它的反边 \(e'\)。
令 \(e\) 代表 \((u, v, w)\)，\(e'\) 代表 \((v, u, w)\)。再设删除 \(e\) 前 \(s, t\) 两点最短距离 \(d(s, t)\)（也就是原图上 dijkstra 的结果）；删除 \(e\) 后 \(s, t\) 两点最短距离为 \(f(s, t)\)；删除 \(e\) 再增加 \(e'\) 后 \(1\) 到 \(n\) 的最短路变为 \(D\)，\(n\) 到 \(1\) 的最短路变为 \(X\)。
那么有：\(D = \min(f(1, n), f(1, v) + w + f(u, n))\)，\(X = \min(f(n, 1), f(n, v) + w + f(u, 1))\)。
证明：\(\min\) 中前半部分为不走 \(e'\) 的最短路，后半部分为必走 \(e'\) 的最短路，合并即可。
如何快速求解 \(f(s, t)\)？事实上我们只关心四种 \(f\)：\(s = 1\) 或 \(s = n\) 或 \(t = 1\) 或 \(t = n\)。我们令 \(T\)，\(R\) 分别代表根为 \(1\) 和为 \(n\) 的两棵最短路树。那么：
- \(e \in T\) 时，\(f(1, v)\) 和 \(f(u, 1)\) 需要重新跑 dijkstra 计算；否则 \(f(1, t) = d(1, t)\)，\(f(s, 1) = d(s, 1)\)。
- \(e \in R\) 时，\(f(n, t)\) 和 \(f(s, n)\) 需要重新跑 dijkstra 计算；否则 \(f(n, t) = d(n, t)\)，\(f(s, n) = d(s, n)\)。
由于 \(T\) 和 \(R\) 边数最多只有 \(199\)，因此上述算法中最多会跑 \(199 \times 2\) 次 dijkstra，可过。
最后枚举 \(e\)，求最小的 \(D + X + k\) 即可，这里 \(k\) 是原题中的 \(D_i\)：把 \(e\) 翻转的代价。
稠密图，dijkstra 不加堆优化（不如不加）。
\(\mathcal{O}(n^3)\)。
代码？拜托了，明天的我！
标签：199,删除,P6880,题解,短路,dijkstra,Luogu,JOI,翻转 From： https://www.cnblogs.com/crab-in-the-northeast/p/luogu-p6880.html