观光
观光
考虑对于每个点维护两个值：最短路和次短路。
记录二者的个数，最后只需判断次短路是否是最短路恰好加上一即可。
由于图不存在负权边，所以不存在呈环状的更新方式。
所以我们实现时可以考虑将一个点拆成两个来写。
- 如果新的距离小于最短路，那么把最短路的信息赋给次短路，然后更新最短路，最后将二者塞进堆中。
- 否则，如果新的距离等于最短路，那么增加方案数即可。
- 否则，如果新的距离小于次短路，更新次短路，最后将其塞进堆中。
- 否则，如果新的距离等于次短路，那么增加方案数即可。
考虑对于每个点维护两个值：最短路和次短路。
记录二者的个数，最后只需判断次短路是否是最短路恰好加上一即可。
由于图不存在负权边，所以不存在呈环状的更新方式。
所以我们实现时可以考虑将一个点拆成两个来写。