自动搬运

查看原文

来自洛谷，原作者为

	wsyhb **

搬运于2025-08-24 21:56:04，当前版本为作者最后更新于2021-08-24 11:19:51，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

巨佬们的题解都好难懂（我是仔细阅读了

个蒟蒻打算写一篇思路清晰、尽可能严谨的题解，如有错误还请指正。

顺带一提，这里有两组 Hack 数据。截止本文发布前（2021.8.25），本题题解区只有 FrenkiedeJong21 的题解能通过这两组数据（当然本题解的代码是可以过的），具体原因见这个帖子。

题意简述

给定 $n$ 个点，$m$ 条边的无向图，以及起点 $S$ 和终点 $T$。求满足下列条件的无序点对 $(A,B)$ 的数量。

条件：对于任意一条从 $S$ 到 $T$ 的最短路径，其恰好经过 $A$ 和 $B$ 其中之一。

数据范围：$1 \le n,m \le 5 \times 10^4$，边权 $w$ 满足 $1 \le w \le 10^9$。

P.S. 本题数据可能出现从 $S$ 出发无法到达 $T$ 的情况。根据前人的经验，此时应输出 $\binom{n}{2}=\dfrac{n(n-1)}{2}$。

---

P.S. 为了方便叙述，默认下文中的“路径”“最短路径”等均指“从 $S$ 到 $T$ 的最短路径”。

分析

设 $F(i)$ 表示经过 $i$ 号点的路径数量，那么 $F$ 可以通过正反两次 Dijkstra 求出。

容易想到一个满足题意的必要条件：$F(A)+F(B)=F(T)$，即经过 $A,B$ 两个点的路径数之和等于总路径数。

进一步，答案应为：满足 $F(A)+F(B)=F(T)$ 且不存在一条路径同时经过 $A$ 和 $B$ 的无序点对 $(A,B)$ 的数量。（因为数量之和达到上限，所以只需保证每条路径只经过至多一个点，即：在 $F(A)$ 和 $F(B)$ 中至多一个提供贡献）

由于 $F(A)+F(B)=F(T)$ 是一个简单的数量关系限制，容易处理。于是考虑如何求出不存在一条路径同时经过 $A$ 和 $B$ 的无序点对 $(A,B)$（当然不是一个一个列举出，而是计算出能代表其特征的数据），再计算出其中满足 $F(A)+F(B)=F(T)$ 的数量。

题解

首先任取一条 $S$ 到 $T$ 的最短路径 $P$，那么 $A$ 和 $B$ 中恰好一个在 $P$ 上。不妨设 $A$ 在路径 $P$ 上，则 $B$ 不在路径 $P$ 上。

结论一

对于固定的 $B$，使得 $A$ 和 $B$ 满足特殊性质的全体 $A$，在路径 $P$ 上是连续的一段。（“$x$ 和 $y$ 满足特殊性质”指“不存在一条路径同时经过 $x$ 和 $y$”，下同）

结论一证明

设 $X,Y,Z$ 为路径 $P$ 上顺次（“顺次”指按从 $S$ 到 $T$ 依次经过的顺序，不一定连续，下同）出现的三个点。假设 $X$ 和 $B$，$Z$ 和 $B$ 都满足特殊性质，但 $Y$ 和 $B$ 不满足特殊性质。

那么有两种情况：

1. 存在一条最短路径 $P_1$，先经过 $Y$ 再经过 $B$。
   • 将路径 $P_1$ 从 $S$ 到 $Y$ 的部分用路径 $P$ 从 $S$ 到 $Y$ 的部分替换，得到路径 $P_2$。显然 $P_2$ 也为最短路径，且 $P_2$ 先经过 $X$ 再经过 $B$，这与 $X$ 和 $B$ 满足特殊性质矛盾。
2. 存在一条最短路径 $P_3$，先经过 $B$ 再经过 $Y$。
   • 将路径 $P_3$ 从 $Y$ 到 $T$ 的部分用路径 $P$ 从 $Y$ 到 $T$ 的部分替换，得到路径 $P_4$。显然 $P_4$ 也为最短路径，且 $P_4$ 先经过 $B$ 再经过 $Z$，这与 $Z$ 和 $B$ 满足特殊性质矛盾。

因此假设不成立，则结论一成立。

结论二

设 $X,Y$ 为任意最短路径上顺次出现的两个点，则不存在最短路径先经过 $Y$ 再经过 $X$。

结论二证明

设 $S$ 到 $X$ 的最短距离为 $a$，$X$ 到 $Y$ 的最短距离为 $e$，$Y$ 到 $T$ 的最短距离为 $b$，则 $S$ 到 $T$ 的最短路径距离为 $a+e+b$。再设 $S$ 到 $Y$ 的最短距离为 $c$，$X$ 到 $T$ 的最短路径为 $d$。

假设存在一条先经过 $Y$ 再经过 $X$ 的最短路径，则 $c+e+d=a+e+b$。进一步有 $c \le a$ 且 $d \ge b$，或 $c \ge a$ 且 $d \le b$。

若 $c \le a$，则 $S$ 到 $T$ 存在一条经过 $Y$ 的路径，其长度为 $c+b \le a+b < a+e+b$。

若 $d \le b$，则 $S$ 到 $T$ 存在一条经过 $X$ 的路径，其长度为 $a+d \le a+b < a+e+b$。

这与 $S$ 到 $T$ 的最短距离为 $a+e+b$ 矛盾，因此假设不成立。

故结论二成立。

推论

由结论二可知：把所有最短路径看成有向路径，然后取它们的并集，所形成的有向图是一个 DAG（Directed Acyclic Graph，有向无环图）。

求解不存在路径同时经过 $x$ 和 $y$ 的无序点对 $(x,y)$

将路径 $P$ 上的点顺次记为 $p_1,p_2,\cdots,p_t$，其中 $t$ 为路径 $P$ 上的点数。（Dijkstra 时记录每个点的前驱，即可求出某条最短路径 $P$ 上的 $p_1,p_2,\cdots,p_t$）

由结论一，设路径 $P$ 上和 $i$ 号点有特殊性质的全体点为 $p_{L(i)},p_{L(i)+1},\cdots,p_{R(i)}$（$L(i)>R(i)$ 表示不存在），则有如下等式：

$$L(i)=\max_{p_{_k} \to i}k+1$$ $$R(i)=\min_{i \to p_{_k}}k-1$$

其中条件 $x \to y$ 表示存在先经过 $x$ 再经过 $y$ 的最短路径。

为了便于计算，我们将其改成递推形式：

$$L(i)=\begin{cases} j+1 \quad (i=p_j)\\ \max_{(k,i) \in E}L(k) \quad (\text{otherwise}) \end{cases}$$$$R(i)=\begin{cases} j-1 \quad (i=p_j)\\ \min_{(i,k) \in E}R(k) \quad (\text{otherwise}) \end{cases}$$

其中条件 $(x,y) \in E$ 表示 $x$ 和 $y$ 之间存在直接相连的边，且存在一条最短路径先经过 $x$ 再经过 $y$。

由推论可知，由于有向最短路径的并集形成的图是 DAG，可以使用拓扑排序对 $L$ 和 $R$ 进行转移。（即：只考虑最短路径可能经过的边，进行拓扑排序）

求解其中满足 $F$ 之和等于 $F(T)$ 的无序点对数量

由上一部分知，所有的、不存在路径同时经过 $x$ 和 $y$ 的无序点对 $(x,y)$ 为全体 $(i,p_j)$，其中 $i$ 不在路径 $P$ 上且 $j \in [l(i),r(i)]$。

至此，只需解决最后一个问题：对于每个 $i$，求出满足 $j \in [l(i),r(i)]$ 且 $F(i)+F(p_j)=F(T)$ 的 $j$ 的数量。

拿一个 map 当桶，在计算 $p_{l(i)}$ 的贡献前把值 $F(i)$ 加入，在计算 $p_{r(i)}$ 的贡献后把值 $F(i)$ 删除，$F(i)+F(p_j)=F(T)$ 的 $i$ 的数量即为计算时 map 中值 $F(T)-F(p_j)$ 的数量。

注意：在本题的限制下，起点 $S$ 到终点 $T$ 的最短路径数量 $F$ 可以达到指数级别。因此，要将最短路径的数量 $F$ 对大质数取模，否则可以被【前言】中提到的 Hack 数据 Hack。

时间复杂度分析

堆优化 Dijkstra 是 $O(m\log{m})$ 的，拓扑排序是 $O(m)$ 的，map 的加入、删除、查询次数为 $O(n)$，因此总时间复杂度为 $O(m\log{m}+n\log{n})$。

代码

#include<bits/stdc++.h>
using namespace std;
int n,m,S,T;
const int max_n=5e4+5;
const int max_m=5e4+5;
int End[max_m<<1],Last[max_n],Next[max_m<<1],Len[max_m<<1],e;
inline void add_edge(int x,int y,int z)
{
	End[++e]=y,Next[e]=Last[x],Last[x]=e,Len[e]=z;
	End[++e]=x,Next[e]=Last[y],Last[y]=e,Len[e]=z;
}
typedef pair<long long,int> P;
priority_queue<P,vector<P>,greater<P> > Q;
long long dis[2][max_n];
const int mod=1e9+7;
inline void add(int &a,int b)
{
	a=a+b-(a+b>=mod?mod:0);
}
inline int get_dif(int a,int b)
{
	return a-b+(a<b?mod:0);
}
int f[2][max_n],pre[max_n];
inline void Dijkstra(int op)
{
	for(int i=1;i<=n;++i)
		dis[op][i]=1e18;
	if(!op)
	{
		dis[op][S]=0,f[op][S]=1;
		Q.push(P(0,S));
	}
	else
	{
		dis[op][T]=0,f[op][T]=1;
		Q.push(P(0,T));
	}
	while(Q.size())
	{
		long long d=Q.top().first;
		int x=Q.top().second;
		Q.pop();
		if(dis[op][x]<d)
			continue;
		for(int i=Last[x];i;i=Next[i])
		{
			int y=End[i];
			if(d+Len[i]<dis[op][y])
			{
				dis[op][y]=d+Len[i];
				f[op][y]=f[op][x];
				if(op)
					pre[y]=x;
				Q.push(P(dis[op][y],y));
			}
			else if(d+Len[i]==dis[op][y])
				add(f[op][y],f[op][x]);
		}
	}
}
inline bool check(int op,int x,int y,int w)
{
	return dis[op][x]+w+dis[op^1][y]==dis[0][T];
}
int p[max_n],tot,l[max_n],r[max_n],d[max_n],que[max_n],head,tail;
inline void TopSort(int op)
{
	for(int x=1;x<=n;++x)
		for(int i=Last[x];i;i=Next[i])
		{
			int y=End[i];
			if(check(op,x,y,Len[i]))
				++d[y];
		}
	head=1,tail=0;
	for(int i=1;i<=n;++i)
	{
		if(!d[i])
			que[++tail]=i;
	}
	while(head<=tail)
	{
		int x=que[head++];
		for(int i=Last[x];i;i=Next[i])
		{
			int y=End[i];
			if(check(op,x,y,Len[i]))
			{
				op?r[y]=min(r[x],r[y]):l[y]=max(l[x],l[y]);
				if(!--d[y])
					que[++tail]=y;
			}
		}
	}
	assert(tail==n);
}
int F[max_n];
vector<int> id_l[max_n],id_r[max_n];
map<int,int> cnt;
int main()
{
	scanf("%d%d%d%d",&n,&m,&S,&T);
	for(int i=1;i<=m;++i)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		add_edge(u,v,w);
	}
	Dijkstra(0);
	if(dis[0][T]==1e18)
	{
		printf("%lld\n",n*(n-1ll)>>1);
		return 0;
	}
	Dijkstra(1);
	for(int i=S;i;i=pre[i])
		p[++tot]=i,l[i]=tot+1,r[i]=tot-1;
	for(int i=1;i<=n;++i)
	{
		if(dis[0][i]+dis[1][i]==dis[0][T])
			F[i]=1ll*f[0][i]*f[1][i]%mod;
		if(!l[i])
			l[i]=1,r[i]=tot;
	}
	TopSort(0),TopSort(1);
	for(int i=1;i<=n;++i)
	{
		if(l[i]<=r[i])
		{
			id_l[l[i]].push_back(i);
			id_r[r[i]].push_back(i);
		}
	}
	long long ans=0;
	for(int i=1;i<=tot;++i)
	{
		for(vector<int>::iterator it=id_l[i].begin();it!=id_l[i].end();++it)
			++cnt[F[*it]];
		ans+=cnt[get_dif(F[T],F[p[i]])];
		for(vector<int>::iterator it=id_r[i].begin();it!=id_r[i].end();++it)
			--cnt[F[*it]];
	}
	printf("%lld\n",ans);
	return 0;
}