题目简述
A.食堂计划 (\(nfls\))
（虽然说A可做且必做，但细节多的题还是可以先放放）
有向图，求不交的最短路组数，无序。
分析 & 性质
最短路跑出来是一个 \(Dag\) ,题目支持 \(O(n ^ 2)\) 的复杂度。可以枚举两个端点dp, 也可以通过两点相交的答案容斥
最终思路
\(sol1:\) \(dp\)，
- 枚举\(u\), \(v\)，通过\(u\)，vdp过程中不交来保证合法。先转移dis小的可保证在转移中能交则必交。
- 保证不重，考虑这样做出来的答案，在 \(dis\) 相等时可能会转移两次，加上限制即可。
- 对于最后的答案，因为 \(n^2\) 枚举（转移会在 \(dp[][]\) 上关于左上右下对角线反复横跳）会造成两次的重复，但是对于 \(S \rightarrow T\)的直接连边不会重复。
\(sol2\) ：容斥
- 考虑构造和答案一样的子问题，发现可以转移，\(x\) 的答案与 \(x\) 反图上能到达的节点的dp值有关。
- 具体为钦定 \(v\) 为交点，然后算出 \(v\) 之后随便走，之前不交的方案，充要性显然。
- \(1D1D\)