好,下面我们再讲一个稍微有一点难度的这个深搜问题,叫做这个
寻路问题。呃,这个寻路问题它是POJ上的1724啊。
它说的是呢有N个城市,然后编号呢是
是1到N,城市之间有R条单向的道路,那每一条单向的道路它连接两个城市,有长度和过路费两个属性。
呃,然后这个Bob他要从1号城市走到N号城市,然后他一共只有K块钱
然后这个问题就是要问你,最短共需要走多长的路,就能够到达N。
当然有可能他钱不够,他就到不了N,对吧?那就这个时候呢你就应该输出一个-1。
>> 对,这个题等于就是不,区别于以往的这种最短路问题,啊它这考虑还有一个费用的限制在里面。
>> 对,啊,那这个规模就是城市呢是最多100个。
呃,这个Bob最多有10000块钱,路呢最多有10000条。
>> 那这个对应的话呢,因为
每一条路有一个长度L和一个过路费T,所以我们在输入数据的时候呢首先当然就输入,输入这个
K,N,R,这样三个分别是,呃城市数、Bob的钱数和这个
路,路一共有多少条。之后的话呢就是对每一条路
都会有这样的一个描述,啊分别是这个路的起始。>>起点是s号。
>> s,啊然后呢这个,呃,e就是终,终点的这个,路连接
的这个终点的城市,啊以及这个对应这条路的长度以及
和它本身的这个费用。>>呃,过路费。那这个路它是单向的,就是说 比如这样一个描述就说明从s有路连到e,从s可以走到e。
但是从e不能走到s,它是单向路。
嗯,那这个题目
到底怎么解决呢?可以用深搜的思路来想,那一个基本的思路就是说,我可以从
以1作为起点,做深度优先搜索 遍历整个图,我肯定会,能够找到一条走到N的路对吧?
>> 对。>>但是我们走到N的路可能有很多很多条。>>那就中间选一个最优的呗。
>> 对,那看起来就应该把所有从1到N的路全部都找出来,然后找一个最短的。
可是这样做的时间复杂度看起来 吓人。>>就TLE了。>>对啊,因为你想从1到N它有多少种走法呀,看着像是一个
这种阶乘级别的事情,啊,所以我们得想两个办法。
>> 那我们最直观想就是,呃大家不知道还记不记得
当时我们在做枚举的时候讲那个什么讨厌的青蛙,啊讲提到
说如果我们本身找到的这个,呃就是你已经
知道当前所走过的这个路径的长度,它已经超过了在之前所找到的这个
呃最优的这个路径长度L,就是说你目前可能还没有达到目标的终点N,就已经超过了
已经达到之前达到N这个终点城市所用的那个最优路径L
那么这个时候的话,你现在所走的这条路其实就已经是,呃不可行的。>>对,没必要再走下去了。
>> 所以那我们,就可以直接,直接就放弃就不用往下走了。>>对。>>所以这是一个重要的一个
呃提前终止这个搜索的一个条件限制。>>呃,那这个条件限制还算
比较好想,但是你光写了这个限制呢实际上还是会超时,啊
这个限制关键就是在于你在探索一条路径的时候,你是时时刻刻
每走到一个城市你就会记录从1走到这个城市花了多少钱,以及
以及走,一共你走了多长,对吧?所以你发现这个长度如果已经超过了 我们前面找过的最优路径的长度,我们就不再往下找了。
这个简之,呃这个称之为简之吧,这个或者说优化,这个优化条件还不够强,所以
我们还得另外再想一个这个优化的条件出来,啊否则就会超时。
那这个优化的条件是什么呢?就是,就是我们啊,还可以用一个二维数组
midL[k][m]啊,这个midL[k][m]这个元素呢它表示
我们走到城市k的时候 如果总的路费是m,正好是m啊,在这种情况下
最优路径的长度,我们把它记在midL[k][m]里面
反正你可能会经过好多条路都能到达k,而且到达k的时候
呃总费用都是m,这就有可能对吧?那在这么多种情况下
那个最优路径的长度,实际上就最短路径的长度我们还记在这个变量里面。>>就是说你实际上就是提前记录了一下对应这个
呃到达城市所对应费用下的这个最短的路径,啊。>>对。那,那由于我们很可能
会多次到达同一个城市,而且多次达到同一个城市的时候我们所花的费用都可能是一样的,对吧。
>> 对。>>那这样的话,如果我下次再走到k的时候,我发现总路费恰好为m
但是这一遍我走到k的时候,总路径长度已经超过了前面记下来的那个
最优值啦,那我们当然就不必再走下去了,对吧。
>> 对。>>那这就是一个优化的办法了。>>所以就可以认为说第二个简之实际上是
对于第一的一个,第一个情况的一个中图版的一个考量。>>呃对,就在每一步骤 呃就是
>> 只要达到某一个城市和某一个费用下,就是看一看说它是不是能够已经 呃pk一下我当前的这个
>> 已前找到的 >> 费用、路径、以及这个长度,啊。
>> 那这个思路有了以后,呃程序呢还算比较好写啦,啊。
那我们来看这个程度哦,呃 这个struct Road它代表一条路,那我们起点呢不用记,只记它的终点
费用,呃长度以及这个费用 然后我们要把这个城市的地图给它存下来,然后我们城市
地图用的是邻接表这种存储方式。
呃我们是用一个vector套vector的这个办法,最终这个地图里面每个元素呢都是一个Road啊
那,那这个比如cityMap[i]它就是一个vector
这个vector里面呢每一个元素都记录着一个城市的信息
这个城市是什么啊?就是从i这个城市有路连过去的那个城市
然后那个城市它当然编号就是d对吧,然后,然后从i到d的费,呃长度是L
费用是t,啊。所以对于每一个
城市,i,我们把从i能一步走到的
经过一条路能走到的那些城市全部都塞到这个cityMap[i]这个
数组,也就是vector里面去。>>对,它表达的是跟i相邻的 那些城市的所有的集合。>>哎,对对,相邻这个词用的很准确哦
嗯,好吧,这个下面我们看这里面minLen这个东西是
嗯,代表我们求得的最优径,一开始我们初始化成无穷大,啊
这个,这个代表的是我当前求得的最优路径的这个长度,就是从1到N的最优路径。
而这个totalLen呢是我正在探索的这条路,呃已经走了多长,啊
然后totalCost就是我正在探索的这条路它已经花了多少钱。
呃visited当然就是说用来标记每一个城市它是不是已经走过
然后这个minL就是我们前面所说的minL[i][j]表示从1到i点的,花销为j的
各种走法里面最短的那条路的长度。
好,接下来我们就做这个深搜啦。
啊我iii,你接着讲。>>我们应该先看那个函数啊。>>好,啊对
要有全局观念啊。>>呵呵,我们首先的话呢,在这个微函数里头当然就是首先让它去输入这个
K,N,R这三个值啦,分别就是,呃
>> 钱、城市数和路的数量,嗯。>>郭老师就,上来就钱。>>呵呵。
>> 这个,接着的话呢我们因为有了对应的这个所有的路是吧?所以我们依次的话呢会分别把这个
对应这个路中间的这个,呃,起始,诶不对,是这个
呃路,这个是路的终点,啊对,我们在这个r.d这个struct里面去定义了终点
呃这个长度和费用,啊。然后这个时候的话呢,我们会去判断一下,如果说呢
我们在这个数据当中可能会出现说,起点和终点是绕圈这样的情况下下,闭锁啦。
那么当这个起点和终点不一致的时候,也就是它确实描述的是把一个
城市和另外一个城市连接起来的时候呢,我们就把这个对应的这个 呃
R这个,这个点呢,就把它放到这个cityMap里面去了,啊。然后呢,完了之后呢我们就会呃
首先去初始化一下这个minL,然后这个minL对应的这个每一个值呢都变成是
呃 >> 一个大数。>>一个大数。之后的话呢还要再去初始化一下这个,呃visit
visited,然后呢也让它都先初始化为0,就是都标记为还没有被访问到。之后这个totalLen
和totalCost呢也会被置为是0,啊。>>正在探索的路它的已经走过的长度和花销。
>> 嗯,然后接着的话呢我们就从这个第一个,呃城市出发。>>对。>>标记一下它的这个visited是
1,表示就是我们就访问到了。>>嗯。>>然后的话呢,这个时候的
它的这个minLen,就是目前位置到达这个目标的
长度,最优长度呢是这个,是一个大数。
之后呢我们就可以去调用这个Dfs函数,啊就是递归地去看这个深搜的过程,然后呢它是从这个
第一个城市出发,那么当你呢这个,如果说确实找到了一条这个
呃最优的路径,那么它是,呃本身是会有一个值的,就会去更新之前的这个,minLen的这个
长度的这个数值,啊。如果它本身,它本身计算出来是有具体的值的话呢,它就会去cout这个minLen的长度
就是我们找到那个最优路径的长度。否则的话呢,就让它去输出,就是如果它没有更新,就始终还是这个
我们自己初始化掉的那个大数的话呢,那么就会cout -1。
>> 就说明找不到从1到N的,呃走得起的路,对吧?>>嗯,对。>>啊,关键这个Dfs
呃。>>您来吧。>>那Dfs啊,就是从s开始向
N进行行走,对吧?那我们看一下如果s已经等于N,那就
这就说明我们已经走到了目标城市了。>>嗯。>>那这个时候当然任务就结束了。
不是说结束了,就我们已经找到了一条路了,这个时候我们就要>>比比>>看看我们找到的这条路,
它总的长度是totalLen,跟我们前面记下来的最优路径MinLen去比较一下,看看要不要更新这个MinLen, 然后我们就返回了。
好了,那如果这个S它不等于它,就说明我还正在行走中,那我就要从S出发,
继续往N这个方向走,那怎么走啊,那当然是要考察所有跟S相邻的那些城市。对吧。
那跟S有路连到的那些城市我们是放在CityMap(s)这个
vector里面了,所以我们就便利这个vector,所以这vector里面的每一个元素,
比如说CityMap(s)[i]实际上它就进入了一个城市,这个城市的标号是d,
那我们把D的值取出来放在这个编程里面,那当然这时候S是有路连到d的,
那我们就看Visited里的d,如果d没有被访问过,我们才试图直接,试图再继续从D往下走对吧,D访问过我们就不管它了。
啊,如果D没有被访问过,那我们要从D再往下走了,那我们要从D再往下走的话,这时候产生的费用是多少呢? 当然就是totalCoast
再加上从这个S走到D的费用,就是这个CityMap(s)[i]变T对吧。>>嗯>>这是,这是 我们从1走到D的费用,就是cost,如果这个cost都已经超过K了,