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