LCP 20. 快速公交
思路：逆向记忆化搜索。思考从target到0所花的最小时间。通过哈希表来进行记忆化搜索，避免重复遍历。细节看注释
class Solution {
public:
typedef long long LL;
typedef pair<LL,LL> PII;
const int mod=1e9+7;
int busRapidTransit(int target, int inc, int dec, vector<int>& jump, vector<int>& cost) {
//小顶堆：first是到达second站点所花的时间
priority_queue<PII,vector<PII>,greater<PII>> qu;
//从target倒着遍历，插入初始状态
qu.push({0,target});
//记忆化搜索，减少不必要的分支
unordered_map<LL,LL> sta;
//记录从0号一步一步到target所花的时间
sta[0]=(LL)target*inc;
//遍历小顶堆
while(qu.size()){
//处理当前所花时间最少的状态
PII tmp=qu.top();
qu.pop();
//如果当前时间比sta[0]还大，那么后续操作都无法让sta[0]更小
if(tmp.first>sta[0]) break;
//如果当前点tmp.second遍历过，那么后续的点一定都是时间大的，直接跳过就行
if(sta.count(tmp.second)) continue;
//记录到当前点的最小距离
sta[tmp.second]=tmp.first;
//记录从0号一步一步到tmp.second所花的时间
sta[0]=min(sta[0],tmp.first+tmp.second*inc);
//记录通过搭乘公交到tmp.second
for(int i=0;i<jump.size();i++){
//tmp.second不能被jump[i]整除，说明搭乘公交后，还需左移或者右移才能到tmp.second
LL t1=tmp.second%jump[i],t2=tmp.second/jump[i];
//可以整除，直接从t2搭乘公交
if(t1==0){
qu.push({tmp.first+cost[i],t2});
}else{
//不可以整除，搭乘公交后，还需左移或者右移
//从t2到达t2*jump[i]后，还需右移t1
qu.push({tmp.first+cost[i]+t1*inc,t2});
//从t2+1到达（t2+1）*jump[i]后，还需左移jump[i]-t1
qu.push({tmp.first+cost[i]+(jump[i]-t1)*dec,t2+1});
}
}
/*这里没有考虑从tmp.second-1移动一步到tmp.second的情况
这是因为考虑了时间复杂度就会o(n)，会超时
我们把这个效果通过sta[0]=min(sta[0],tmp.first+tmp.second*inc);这一步解决掉了。
这里是有贪心的思想存在，因为jump[i]>=2，那么移动的变化>=2，通过纯走路都不能更新，那肯定是因为做公交带来的效果更好。
*/
}
return sta[0]%mod;
}
};