参考: sto

最短路

1. spfa
2. dijkstra
3. heap + dijkstra
4. bfs(w = 1)

最短路计数

if(dp[u] > dp[v] + 1)
    dp[u] = dp[v] + 1;
    cnt[u] = cnt[v];
else if(dp[u] == dp[v] + 1)
    cnt[u] += cnt[v];
需要满足 拓扑序 可以用 dijkstra 或者 bfs
途中不能有边权为 0 的点 所有边权都大于 0

次短路(k 短路)

链接: orz

1. a_star (建反图作为估价函数)
2. spfa
3. dijkstra

次短路计数

1. dijkstra
2. bfs
和最短路计数一样，需要有最短路树，按拓扑序更新
d[i][0] 最短路径  cnt[i][0]
d[i][1] 次短路经  cnt[i][1]