题面

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

数据范围：

2≤n≤1052 \le n \le 10^5

1≤m≤1051 \le m \le 10^5

题目链接

分析

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

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

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

何时变短？

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

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

何时变长？

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

如果我们把 GG 中所有最短路单独拿出来建一张图，我们将会得到一张 DAG 图 G′G' 。

如果 GG 中所有最短路都要经过 ee 边，则 ee 边必然是 G′G' 中的桥。如果 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 边是否在 G′G' 内。

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

完整参考代码

%%%