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