空间换时间
使用一个 map
完成有序地映射,从而在每一层根据出发地选取机票时,都能够优先选取目的地字典序最小的机票,此处本质上是一个图,并且题设告知存在路径。使用一个 unordered_map<string,map<string,int>> tic_map
去进行记录,本质上是 unordered_map<出发地,map<目的地,机票数>> tic_map
。
那么首先在结果数组 res
中加入一个 JFK
作为出发地,那么在每一层递归中只需要在 tic_map[res.back()]
中选取机票,此时优先选到的机票一定是字典序在前的。那么在每次优先选取最优的基础上,那么就一定能够找到最有路径。在找到最有路径后递归结束。