AOJ 1383 - Pizza Delivery

Author Avatar
Jimmy Zhang Oct 06, 2018
  • Read this article on other devices

题面

某座城市里有 nn 个点和 mm单向路径。从某一天开始连续的 mm 天里,第 ii 天会把第 ii 条路径反向,同时在下一天会把这条路径的方向恢复成原方向。某人想从 11 点到 22 点,问在这 mm 天里,第 ii11 点和 22 点间的最短路径相比原图是变长(输出 HAPPY)、变短(输出 SAD)还是不变(输出 SOSO)。

数据范围

2n1052 \le n \le 10^5

1m1051 \le m \le 10^5

题目链接

分析

首先我们可以考虑正向建一张图,同时反向建一张图。我们记原图为 GG,记 dis(u,v)dis(u, v) 代表 uu 点到 vv 点间的最短距离。

我们在正向图中以 11 为源点跑一遍单源最短路,即可得到 11 点到任一点 uu 的最短路径 dis(1,u)dis(1, u);于此同时我们在反向图中以 22 为源点跑一遍单源最短路即可得到任一点 vv22 点的最短路 dis(v,2)dis(v, 2)

下面记当前我们反向的是边 e:(u,v)e:(u, v),反向后是 e:(v,u)e’ : (v, u),其长度为 cc

何时变短?

若最短路变短,则在图 G+eG + e’ 中所有从 11 点到 22 点的最短路一定经过 ee’ 而一定不经过 ee。至于原因,最短路径上显然不可能出现环(即同时包含 eeee’),而如果最短路径经过 ee 的话,那么这条最短路也就是原图 GG 中的最短路了,长度肯定不会发生变化。

在这种情况下,有 dis(1,v)+c+dis(u,2)<dis(1,2)dis(1, v) + c + dis(u, 2) < dis(1, 2)。若满足该条件,则最短路一定变短。反正,一定不变短。

何时变长?

经过上述是否变短的判断,到这一步时我们已经知道最短路不会变短了。

如果我们把 GG 中所有最短路单独拿出来建一张图,我们将会得到一张 DAG 图 GG’

如果 GG 中所有最短路都要经过 ee 边,则 ee 边必然是 GG’ 中的桥。如果 ee 边被反向了,那么最短路长度一定改变,即变长。

接下来就是如何判断 ee 边是否为桥了。

num(u,v)num(u, v) 代表 uu 点到 vv 点最短路的方案数,若有 num(1,u)num(v,2)=num(1,2)num(1, u) \cdot num(v, 2) = num(1, 2) 则表明所有最短路一定经过 ee 边,即 ee 边为桥。

何时不变?

既不变长又不变短…… 当然就是不变啦(逃

实现

实现的时候我们不必要真的把最短路上所有边拿出来单独建图。我们可以通过判断 dis(1,u)+c+dis(v,2)dis(1, u) + c + dis(v, 2) 是否等于 dis(1,2)dis(1, 2) 来得知 ee 边是否在 GG’ 内。

统计最短路方案数可以随跑 Dijkstra 算最短路时同时完成(Dijkstra 本质就是个 DP,对吧)。需要注意的是,记录和判断最短路方案数的时候为了防止爆 long long 应当取模后比较。

完整参考代码

%%%

This blog is under a CC BY-NC-SA 4.0 Unported License.
Link to this article: https://blog.codgician.pw/2018/10/06/aoj-1383/