题意

给定一个无向图,每一个点有点权,求最短路条数以及最短路上可能的最大边权。

分析

除了计算最短路之外,需要计算出最短路条数以及最短路中可能的最大点权,这两个问题都可以通过动态规划完成。这两个问题实际上应该在dijkstra的松弛操作中完成,因为发生松弛时,说明产生了新的最短路。

对于前者,很容易想到为每一个点维护一个状态num[],即到该点的最短路条数,那么$num[i] = \sum_{v是i的邻居,并且在和i在同一条最短路上}num[i]$。

对于后者,为每一个点定义一个最大点权p[],更新方程类似,此处留给读者思考吧。