分层图:可以理解为有多个平行的图。
适用场景:题目对边的权值提供可选的操作,比如可以将一定数量的边权减半
一般模型是:在一个正常的图上可以进行 k 次决策,对于每次决策,不影响图的结构,只影响目前的状态或代价。一般将决策前的状态和决策后的状态之间连接一条权值为决策代价的边,表示付出该代价后就可以转换状态了。
对于分层图的构建步骤可以描述为:
1、先将图复制成 k+1 份 (0 ~ k)
2、对于图中的每一条边 <u,v> 从 ui 到 vi+1 建立与题目所给操作相对应的边(i=0,1,…,k)
k代表了进行操作的次数,而每层之间点的关系代表了何时进行操作。
例如:有带权边 <u,v> = w, 可选操作:修改权值为0
让第 i 层的点 u 向 i+1 层的点 v连一条边权为 0 的边。
一般有两种方法解决分层图最短路问题:
建图时直接建成k+1层。
我们建k+1层图。然后有边的两个点,多建一条到下一层边权为0的单向边,如果走了这条边就表示用了一次机会
有N个点时,1n表示第一层,(1+n)(n+n)代表第二层,(1+2n)(n+2*n)代表第三层,(1+i*n)(n+in)代表第i+1层。因为要建K+1层图,数组要开到n * ( k + 1),点的个数也为n * ( k + 1 ) 。
多开一维记录机会信息
我们把dis数组和vis数组多开一维记录k次机会的信息。
dis[ i ][ j ] 代表到达 i 用了 j 次免费机会的最小花费.
vis[ i ][ j ] 代表到达 i 用了 j 次免费机会的情况是否出现过.
更新的时候先更新同层之间(即花费免费机会相同)的最短路,然后更新从该层到下一层(即再花费一次免费机会)的最短路。
时间复杂度:O(k*(m+n)log(n))