作者推荐
【广度优先搜索】【网格】【割点】【 推荐】1263. 推箱子
LCP 20. 快速公交
小扣打算去秋日市集，由于游客较多，小扣的移动速度受到了人流影响：
小扣从 x 号站点移动至 x + 1 号站点需要花费的时间为 inc；
小扣从 x 号站点移动至 x - 1 号站点需要花费的时间为 dec。
现有 m 辆公交车，编号为 0 到 m-1。小扣也可以通过搭乘编号为 i 的公交车，从 x 号站点移动至 jump[i]*x 号站点，耗时仅为 cost[i]。小扣可以搭乘任意编号的公交车且搭乘公交次数不限。
假定小扣起始站点记作 0，秋日市集站点记作 target，请返回小扣抵达秋日市集最少需要花费多少时间。由于数字较大，最终答案需要对 1000000007 (1e9 + 7) 取模。
注意：小扣可在移动过程中到达编号大于 target 的站点。
示例 1：
输入：target = 31, inc = 5, dec = 3, jump = [6], cost = [10]
输出：33
解释： 小扣步行至 1 号站点，花费时间为 5； 小扣从 1 号站台搭乘 0 号公交至 6 * 1 = 6 站台，花费时间为 10； 小扣从 6 号站台步行至 5 号站台，花费时间为 3； 小扣从 5 号站台搭乘 0 号公交至 6 * 5 = 30 站台，花费时间为 10； 小扣从 30 号站台步行至 31 号站台，花费时间为 5； 最终小扣花费总时间为 33。
示例 2：
输入：target = 612, inc = 4, dec = 5, jump = [3,6,8,11,5,10,4], cost = [4,7,6,3,7,6,4]
输出：26
解释： 小扣步行至 1 号站点，花费时间为 4； 小扣从 1 号站台搭乘 0 号公交至 3 * 1 = 3 站台，花费时间为 4； 小扣从 3 号站台搭乘 3 号公交至 11 * 3 = 33 站台，花费时间为 3； 小扣从 33 号站台步行至 34 站台，花费时间为 4； 小扣从 34 号站台搭乘 0 号公交至 3 * 34 = 102 站台，花费时间为 4； 小扣从 102 号站台搭乘 1 号公交至 6 * 102 = 612 站台，花费时间为 7； 最终小扣花费总时间为 26。
提示：
1 <= target <= 109
1 <= jump.length, cost.length <= 10
2 <= jump[i] <= 106
1 <= inc, dec, cost[i] <= 106
单源路径
分析从0到x的最小花费时间。
情况一：没有坐公交，inc*target。
情况二：做了公交，枚举最后一趟公交i，对于公交只需要考虑三种情况：
1，x就在公交站，就在x下车。
2，在x的前一站下车，x/ jump[i]*jump[i]。
3，在x的后一站下车x/ jump[i]*jump[i]+1。
假定x的前一站是x1，前前一站是x2。
{ x 2 / j u m p [ i ] → i n c x 1 / j u m p [ i ] → c o s t [ i ] x 1 i n c + c o s t [ i ] x 1 下车 x 2 / j u m p [ i ] → c o s t [ i ] x 2 → i n c × j u m p [ i ] x 1 i n c ∗ j u m p [ i ] + c o s t [ i ] x 2 下车 \begin{cases} x2/jump[i]^{inc}_{\rightarrow} x1/jump[i]^{cost[i]}_{\rightarrow} x1 & inc+cost[i] & x1下车\\ x2/jump[i] ^{cost[i]}_{\rightarrow} x2 ^{inc\times jump[i]}_{\rightarrow} x1 & inc*jump[i]+cost[i] & x2下车 \end{cases}{x2/jump[i]→incx1/jump[i]→cost[i]x1x2/jump[i]→cost[i]x2→inc×jump[i]x1inc+cost[i]inc∗jump[i]+cost[i]x1下车x2下车
情况三证明类似。
共四种情况：
{ 直接处理 没坐车 出发站点 刚好在站点 2 个下车站点 不在车站 \begin{cases} 直接处理 & 没坐车\\ 出发站点 & 刚好在站点\\ 2个下车站点 & 不在车站\\ \end{cases}⎩⎨⎧直接处理出发站点2个下车站点没坐车刚好在站点不在车站
堆优化的单源路径
由于节点数未知，所以无法用朴素单源路径。初始状态无法知道起点(0)的相连节点，所以求0的最短路径，只能求target的最短路径。
代码
核心代码
typedef pair<long long, int> PAIRLLI; class Solution { public: int busRapidTransit(int target, int inc, int dec, vector<int>& jump, vector<int>& cost) { std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap; minHeap.emplace(0, target); while (minHeap.size()) { const long long llDist = minHeap.top().first; const int iCur = minHeap.top().second; minHeap.pop(); if (m_mDis.count(iCur)) { continue; } m_mDis[iCur] = llDist; if (0 == iCur) { break; } minHeap.emplace(llDist+(long long)inc*iCur, 0); for (int i = 0 ; i < jump.size(); i++) { const int x1 = iCur / jump[i] * jump[i]; if (x1 != iCur) { minHeap.emplace(llDist + ((long long)inc) * (iCur - x1) , x1 ); minHeap.emplace(llDist + ((long long)dec) * (x1 + jump[i] - iCur),x1 +jump[i]); } else { minHeap.emplace(llDist + cost[i], x1/jump[i]); } } } return m_mDis[0]%1000'000'007; } unordered_map<int, long long> m_mDis; };
测试用例
template<class T,class T2> void Assert(const T& t1, const T2& t2) { assert(t1 == t2); } template<class T> void Assert(const vector<T>& v1, const vector<T>& v2) { if (v1.size() != v2.size()) { assert(false); return; } for (int i = 0; i < v1.size(); i++) { Assert(v1[i], v2[i]); } } int main() { int target, inc, dec; vector<int> jump, cost; { Solution sln; target = 31, inc = 5, dec = 3, jump = { 6 }, cost = { 10 }; auto res = sln.busRapidTransit(target, inc, dec, jump, cost); Assert(33, res); } { Solution sln; target = 612, inc = 4, dec = 5, jump = { 3, 6, 8, 11, 5, 10, 4 }, cost = { 4, 7, 6, 3, 7, 6, 4 }; auto res = sln.busRapidTransit(target, inc, dec, jump, cost); Assert(26, res); } { Solution sln; target = 1000000000, inc = 1, dec = 1, jump = { 2 }, cost = { 1000000 }; auto res = sln.busRapidTransit(target, inc, dec, jump, cost); Assert(10953125, res); } { Solution sln; target = 954116209, inc = 725988, dec = 636911, jump = { 524425, 158389 }, cost = { 41881, 941330 }; auto res = sln.busRapidTransit(target, inc, dec, jump, cost); Assert(556489627, res); } }
小优化
可以跳过下车站，直接处理上车站。性能更优化，但排错难道增加。
typedef pair<long long, int> PAIRLLI; class Solution { public: int busRapidTransit(int target, int inc, int dec, vector<int>& jump, vector<int>& cost) { std::priority_queue<PAIRLLI, vector<PAIRLLI>, greater<PAIRLLI>> minHeap; minHeap.emplace(0, target); while (minHeap.size()) { const long long llDist = minHeap.top().first; const int iCur = minHeap.top().second; minHeap.pop(); if (m_mDis.count(iCur)) { continue; } m_mDis[iCur] = llDist; if (0 == iCur) { break; } minHeap.emplace(llDist+(long long)inc*iCur, 0); for (int i = 0 ; i < jump.size(); i++) { const int x1 = iCur / jump[i] * jump[i]; minHeap.emplace(llDist + ((long long)inc) * (iCur - x1) + cost[i], x1 / jump[i]); if (x1 != iCur) { minHeap.emplace(llDist + ((long long)dec) * (x1 + jump[i] - iCur) + cost[i], x1 / jump[i] + 1); } } } return m_mDis[0]%1000'000'007; } unordered_map<int, long long> m_mDis; };
2023年3月版
class Solution {
public:
const long long M = 1e9 + 7;
int busRapidTransit(int target, int inc, int dec, vector& jump, vector& cost) {
std::priority_queue<std::pair<long long, int>, std::vector<std::pair<long long, int>>, std::greater<std::pair<long long, int>>> que;
std::unordered_map<int,long long> mPosTime;
auto append = [&](long long llTime, int iPos)
{
bool bHas = mPosTime.count(iPos);
if (bHas && (llTime >= mPosTime[iPos]))
{
return;
}
que.emplace(llTime, iPos);
mPosTime[iPos] = llTime;
};
append(0, target);
long long llRet = inc * (long long)target;
for (; que.size()😉
{
const long long llTime = que.top().first;
const int iPos = que.top().second;
que.pop();
if (llTime > llRet)
{
break;
}
llRet = min(llRet, llTime + inc*(long long)iPos);
for (int i = 0; i < jump.size(); i++)
{
const int iPreCur = iPos / jump[i] * jump[i];
if (iPreCur == iPos)
{
append(llTime + cost[i], iPos / jump[i]);
continue;
};
append(llTime + cost[i] + (long long)inc*(iPos - iPreCur), iPos / jump[i]);
const int iNext = iPreCur + jump[i];
append(llTime + cost[i] + (long long)dec*(iNext - iPos), iPos / jump[i] + 1);
}
}
return llRet % M;
}
};
