C++Leetcode--787. K 站中转内最便宜的航班

题目描述

官方描述(中文)
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);
	}
};