黑暗城堡

题意：https://loj.ac/p/10064

先求出\(1\)到每个点的最短路，然后按照结点\(dis[]\)值排序，从小到大依次考虑每个点有多少种转移方案。

在最小生成树Prim的过程中，记 已确定最短路的点集\(S\)，未确定的为\(T\)。对于点\(T\)中\(dis\)最小的点\(u\)，遍历\(S\)中有多少\(v\)满足\(dis[v]+w_{u,v}=dis[u]\)即可。

时间复杂度\(O(n^2)\)。

图论杂题