type
status
date
slug
summary
tags
category
icon
password
洛谷P4568
给你一张带权图，你可以用不大于 次机会免费通过一条边(或者是以其他费用通过)，问你从起点到终点最短路径花费？
分层最短路就是用来处理这一问题的,其实就是变了点形的dp，只是名字高级了一点。无非就是设 ，其意就是到达 点用了 次机会所用的最小花费。
而分层最短路大概就是把图扩充为好几层，每一层代表的含义就是使用了几次机会。如果到了下一层那么就是免费（或其他），在这一层里走就是正常花费。其实还是挺好理解的(ps：只是把二维的 变成了一维)。