• 最短路径\(dag\)一道好题。
• 题目大意：求一张图中满足下列要求的点对\((i,j)\)数量：
• 所有最短路径必定会经过 \(i\) 点和 \(j\) 点中的任意一点
• 不存在一条最短路同时经过 \(i\) 点和 \(j\) 点。
• 首先所有最短路要么经过\(i\)点要么经过\(j\)点，不存在两个都不经过或者都经过的
• 所以经过\(i\)点的最短路方案加上经过\(j\)点的最短路方案不存在交集。
• 那么栲虑怎么求最短路方案先做一边\(dij\)，然后在\(tag\)上\(dp\)方案数即可正反都做一遍。
• 这个满足了还不够因为这个只是\(i,j\)的必要条件，还不是充分条件
• 关键在于所有的路径不能同时经过这两个点。
• 转移拓扑排序实现即可