[LintCode]Gas Station II

Gas Station的变形题。这套题需要我们找最少的加油的次数，如果我们当前在加油站i，剩余油量r，那么我们可以轻易地找到这个状态下可以到达的下一个加油站，只要下一个的加油站的距离小于等于dist[i] + r即可。如果我们把这个状态看做一个节点，那么就有一条从当前加油站到下一个加油站的无权有向边连接他们。那么我们在这个图上作BFS找最短路径即可得到最少的加油次数。我们用当前所在的加油站的index和剩余的油量定义一个节点，起始状态为(0, original)，如果BFS的过程中我们发现距离超过了target，那么我们就找到了最短路径。假设输入数组长度为N，时间复杂度O(V + E)，顶点数为N，边最多可能有N^2个，所以时间复杂度最坏O(N^2)，空间复杂度O(N)，代码如下：

	class Solution {
	public:
	/**
	* @param target: The target distance
	* @param original: The original gas
	* @param distance: The distance array
	* @param apply: The apply array
	* @return: Return the minimum times
	*/
	int getTimes(int target, int original, vector<int> &distance, vector<int> &apply) {
	int len = distance.size(), layer = 0;
	queue<pair<int, int>> q;
	q.emplace(-1, original);
	while (q.size())
	{
	int sz = q.size();
	for (int i = 0; i < sz; ++i)
	{
	auto node = q.front();
	q.pop();
	vector<pair<int, int>> adjs;
	//get all adjacent nodes(reachable nodes)
	int idx = node.first, remain = node.second, dist = idx < 0? 0: distance[idx], len = distance.size();
	if(idx >= 0)remain += apply[idx];
	if (dist + remain >= target)return layer;
	for (int i = idx + 1; i < len; ++i)
	{
	if (distance[i] > dist + remain)break;
	adjs.emplace_back(i, remain - (distance[i] - dist));
	}
	for (const auto& adj : adjs)q.push(adj);
	}
	++layer;
	}
	return -1;
	}
	};

view raw Gas Station II.cpp hosted with ❤ by GitHub