【x日x题】PAT 1003 dijkstra模板
/ / 点击 / 阅读耗时 1 分钟题意
给定一个无向图,每一个点有点权,求最短路条数以及最短路上可能的最大边权。
分析
除了计算最短路之外,需要计算出最短路条数以及最短路中可能的最大点权,这两个问题都可以通过动态规划完成。这两个问题实际上应该在dijkstra的松弛操作中完成,因为发生松弛时,说明产生了新的最短路。
对于前者,很容易想到为每一个点维护一个状态num[]
,即到该点的最短路条数,那么$num[i] = \sum_{v是i的邻居,并且在和i在同一条最短路上}num[i]$。
对于后者,为每一个点定义一个最大点权p[]
,更新方程类似,此处留给读者思考吧。
感谢阅读!欢迎评论嗷~