[最短路] [计数] [ARC090E] Avoiding Collision

· · 个人记录

考虑容斥：不相遇方案 = 总方案 - 相遇方案。

考虑求总方案，预处理 dis_i,dis2_i,cnt_i,cnt2_i，表示

考虑给相遇方案分类，显然不能将每条边的方案相加，这样重合端点会算重，不妨分为点上相遇和边（不包括两端点）上相遇。 1. 点：条件是 $dis_i+dis2_i=dis_t$，方案为 $(cnt_i*cnt2_i)^2$。 2. 边：条件可转换为存在某一时刻，使得两点均在边（不包括两端点）上，正确性显然，那么两点在该边的时间段分别为 $[dis_u,dis_u+w]$ 和 $[dis2_v,dis2_v+w]$，判断区间相交即可。即：$dis_u+w>dis2_v$ 且 $dis2_v+w>dis_u$。方案数：$(cnt_u*cnt2_v)^2$。