ZOJ题目页面传送门

给定一个有向图\(G=(V,E),n=|V|,m=|E|\)（可能有重边和自环，节点从\(0\)开始编号），以及\(q\)组询问，对于每组询问你需要回答有多少条从节点\(0\)开始的最短路经过节点\(x\)（节点\(0\)到某一个节点的最短路可能不唯一），输出答案的后\(10\)位。有多组数据。

\(q,n\in[1,10^4],m\in[1,5\times10^4]\)，边权为正。

既然题目要数最短路的个数，我们可以把那些不在最短路上的边去掉，只保留在最短路上的边，构造出一个新图\(G'=(V,E')\)。这样问题就转化成了在\(\bm G'\)上有多少条从节点\(\bm0\)开始的路径经过节点\(\bm x\)（显然的吧）。那怎么知道那些边该留那些边不该留呢？我们可以先跑一边堆优化Dijkstra求出到节点\(0\)的最短路长度数组\(dis\)，那么\(E'=\{(x,y,len)|(x,y,len)\in E,dis_y=dis_x+len\}\)。

接下来我们就要求在\(\bm G'\)上有多少条从节点\(\bm0\)开始的路径经过节点\(\bm x\)了。我们考虑将一条从节点\(0\)开始、经过节点\(x\)、终点为\(y\)的路径拆成两段：\(0\to x,x\to y\)，对它们分别计数，最后相乘即可。很显然，\(G'\)是无环的，也就是一个DAG（因为边权为正），这样就可以在\(G'\)上DP了。设\(dp1_i\)表示路径\(0\to x\)的个数，\(dp2_i\)表示以\(x\)为起点的路径（即\(\sum\limits_{y\in V}\text{路径}x\to y\text{的个数}\)）。状态转移方程显然是：

\[ \begin{aligned} dp1_i&=\begin{cases}1&i=0\\\sum\limits_{(j,i,len)\in E'}dp1_j&i>0\end{cases}\\ dp2_i&=\sum_{(i,j,len)\in E'}dp2_j+1 \end{aligned} \]

可这是一个图啊，DP顺序是什么呢？容易发现，要想知道\(dp1_i\)，得先知道\(\forall j\left((j,i,len)\in E'\right)\)，所以要按照拓扑序DP；\(dp2\)反之，要按照拓扑逆序DP。（如果你懒得写拓扑排序，也可以记忆化搜索）