ARC090C Avoiding Collision

题意：给出一张含有 个点 条带权边的无向图。

有两人分别在 ，他们要前往对方的位置。

求两人都走最短路且不相遇（点上和边上相遇都不行）的方案数。答案对 取模。

，，时限 。

---

建立从 的最短路 。

记 为 的最短路径数， 为 的最短距离。

类似地定义 。

记 ，记 之间的最短路长度。

若允许两人相遇，则方案数为两个 路径数的乘积。即 。

考虑容斥，减去不合法的方案。

不难发现，在走最短路的基础上，两人若相遇，只能相遇一次。

枚举在那个点或那条边上相遇：

• 在点 上相遇

  条件： 且

  方案数：

• 在边 上相遇（不包括端点）（注意 可以交换）

  条件： 且

  方案数：

复杂度 。