题目描述
官方描述(中文)
2021/08/24每日一题
思路
深搜加记忆
- 为了通过这个题我错了8次。。。开始对题意的理解不清楚导致多次提交出错。一开始只单纯使用深搜,不出意外超时了。
- 之后开始考虑使用深搜加记忆,一开始使用单纯的一个map存储访问的节点key->站点id,value->由该点到达终点所需的最小值,当再次访问到这个结点之后,去map中寻找看一下这个节点是否已经访问过了,如果已经访问过直接返回。但这个处理方法忽略一个关键条件k,如果第一次访问到i节点并且此时从该节点没有办法在剩余的k步内到达终点,那么在之后访问到这个节点后,判断这个节点已经被访问过了,会直接返回无法到达,导致其实可以到达的路径被忽略了。
- 知道了关键信息k,就可以基于k和i建立数据结构std::map<int, std::map<int,int>>.外层的map key依旧是站点id,第二个map内存储的是到达i点剩余k以及在k步内该节点到达终点的所需的最小值。当发现第i节点剩余k步的条件已经被访问过了,就可以直接放回。
代码
class Solution
{
public:
using MapDstPrice = std::map<int, std::vector<std::pair<int, int>>>;
using MapMap = std::map<int, std::map<int, int>>;
int Dfs(MapDstPrice& mapDstP, MapMap& visitedPrice, int from, int dst, int k)
{
if (k < 0)return -1;
if (from == dst)return 0;
if (visitedPrice.find(from) != visitedPrice.end())
{
auto& mapTemp = visitedPrice[from];
if (mapTemp.find(k) != mapTemp.end())
{
return mapTemp[k];
}
}
int minPrice = -1;
for (const auto iter : mapDstP[from])
{
auto tempPrice = Dfs(mapDstP, visitedPrice, iter.first, dst, k - 1);
if (tempPrice == -1)continue;
tempPrice += iter.second;
minPrice = (minPrice == -1) ? tempPrice : min(minPrice, tempPrice);
}
visitedPrice[from][k] = minPrice;
return minPrice;
}
int findCheapestPrice(int n, vector<vector<int>>& flights, int src, int dst, int k)
{
MapDstPrice mapDstP;
for (auto vec : flights)
{
if (vec.size() < 3)continue;
mapDstP[vec[0]].push_back({ vec[1], vec[2] });
}
MapMap visitedPrice;
return Dfs(mapDstP, visitedPrice, src, dst, k + 1);
}
};
执行结果
dfs+记忆 执行结果惨不忍睹,滚去学dp了。dp yyds
Q.E.D.