容易想到的做法是，对每次询问，遍历每条边，看这条边是否在$u,v$的最短路上，只需判断d[u] + w == d[v]是否成立即可。但这样的做法是$O(qm)=O(n^4)$的，稳稳的TLE。究其原因，是因为计数的时候不够高效。这种每找到合法边时就+1的策略，可以卡到每次遍历$O(n^2)$条边，举一个例子，对18个点的图，将17放在最左边，18放在最右边，剩下的点从小到大4个一列摆放，然后记17在第一层，1,2,3,4在第二层，…，18在第六层。之后同一层内的点之间不连边，不同层间连一条长为层数差的边，我们就得到了一个$O(n^2)$级别边数，且每条边都在某条最短路上的图。每次都这样询问就会达到复杂度上界。举这个例子不是为了特判这种情况并打表过掉（真的可以吗？），而是为了说明这种对每个点对枚举所有边的做法枚举效率太低了。考虑如何降低到$O(qn)$级别的复杂度。一种想法是，既然定源汇最短路和单源最短路可以同时解决，那么定源汇最短路边数能不能和单源最短路边数同时解决呢？换句话说，一次单源最短路边数的统计结果，能不能想办法应用到不同终点处？最终经过某种思考，对每个指定的$s$，我们将最短路中的边用其终点标记。这句话的想法是，对某个指定的$t$，如果该边终点$v$在$s,t$最短路上，那么由于该边在$s,v$最短路上，而$v,t$最短路是某条$s,t$最短路的一部分，也就一定可以构造一条$s,t$最短路使它包含该边。最终的做法是，对每个源$s$，只沿满足$d[v]=d[u]+w$的边$(u,v)$做某种bfs，这是为了满足拓扑序在前的先遍历，拓扑序在后的后遍历。遍历过程是，每次从堆中取出结点，只沿满足条件的边前进，在终点上计数器+1，若堆中没有终点，将其终点加入按d排列的小顶堆。直至堆为空。最后获取答案$s,t$时，遍历所有点，将每个满足$d[s][u]+d[u][t]$的点u的计数器加到答案中。由于每条边只由其终点标记，这样计数是不重不漏的。成功降低至$O(q,n)$复杂度。