【图论】【堆优化的单源路径】LCP 20. 快速公交

作者推荐

【广度优先搜索】【网格】【割点】【推荐】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 <= 10⁹
1 <= jump.length, cost.length <= 10
2 <= jump[i] <= 10⁶
1 <= inc, dec, cost[i] <= 10⁶

单源路径

分析从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。
$\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}$
情况三证明类似。

共四种情况：
$\begin{cases} 直接处理 & 没坐车\\ 出发站点 & 刚好在站点\\ 2个下车站点 & 不在车站\\ \end{cases}$

堆优化的单源路径

由于节点数未知，所以无法用朴素单源路径。初始状态无法知道起点(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;
}

};

扩展阅读

视频课程

有效学习：明确的目标及时的反馈拉伸区（难度合适），可以先学简单的课程，请移步CSDN学院，听白银讲师（也就是鄙人）的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了，为老板分忧，请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

我想对大家说的话
闻缺陷则喜是一个美好的愿望，早发现问题，早修改问题，给老板节约钱。
子墨子言之：事无终始，无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙，那算法就是他的是睛