dijkstra 边找最短路,边做dp. 题目不光要找最短路还要找有多少条最短路。在使用 dijkstra 进行最短路的时候顺便更新dp, 即:

  • dis[u] + w[u][v] < dis[v] => f[v] = f[u]
  • dis[u] + w[u][v] = dis[v] => f[v] += f[u]