[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)，代码如下：