090E

果然自己想出来和看题解做出来是完全不同的感觉…… 首先考虑没有不相遇的限制条件怎么做。发现这个问题就是 P1144 再加上乘法原理。 然后思考如何处理相遇的情况。容易想到枚举相遇的点和边。首先从 $s$ 和 $t$ 开始各跑一遍最短路，$dis_{u,0/1},cnt_{u,0/1}$ 分别为点 $ ......