最近遇到了好多这样的题,感觉应该是一类题.
这一类问题就是要求满足某一限制条件下的最短路,比如每一条边都有两种边权,要求路径上其中一种边权之和小于某个值的条件下的另一个边权最小的路径.
可以用状态的思想考虑,在dp时,状态设计的不好就会出现这样类似的问题,不好转移,dp中解决这种问题的方法就是重新定义状态.在这个图中,我们也可以重新定义节点.本来节点只有节点编号这个属性,我们把被限制条件限制的边权和加入到属性中,这样只需要在最后只考虑属性中的这一个边权和满足条件的节点就行了.对应到图上,就是把一个点拆成很多点,拆成的每一个点对应原来点限制边权不同时的状态.
举个例子,考虑这样一个图:每一条边有距离和花费,要求花费小于等于K的最短路.可以把图中的每一个点拆成K个点,每一个点对应经过原来点是花费了一个数的状态.这样只需要在这个新图中跑一个最短路,用距离当边权,最后寻找终点拆出的点中对应花费小于K的点的最短路.
其实拆点只是一个思考方式,真正写的时候不需要写拆点的代码,可以把点的编号(x)变成一个二维数据(x,k),把这一个二维数据看作是点的编号,代表x这个点拆成的对应花费为k的点.反映在dijkstra中,就是优先队列中原本的Node{d,x},d是源点到x点的距离,变成Node{d,x,k},d是源点到点(x,k)的距离.在松弛操作中,原本的三角不等式写成dis[to] > dis[x] + e.d,其中dis的下标是点的编号.现在把点的编号作为二维数据考虑,就是disto > disx + e.d,其中x和cost分别对应当前所在点的编号和到这个点的花费,换句话说,就是新图中这个点的二维编号.
模板题:
Environment-Friendly Travel: https://codeforces.com/group/2l2uaz0vCx/contest/102501/problem/A
题意是在二维平面中,给你N个中转点和一个起点一个终点共N+2个点的坐标,中转点之间有一些点之间有一些交通方式,这些交通方式经过的距离都是两个点的欧几里得距离,但是每一种交通方式平均每单位距离的碳排放量不一样.同时你可以从起点开始,开汽车到任何一个点,然后经过各种交通方式折腾,在一个点开汽车到终点,这也是起终点和中转点的唯一交通方式,并且中转点之前不能用汽车,汽车也有碳排放量.让你求在经过距离小于B的情况下碳排放量最小的路径,坑点在于可以直接开车从起点到终点.就是个二维最短路模板题.