题解：洛谷P3403 跳楼机

洛谷

同余最短路，话说博主图论很烂，所以来做一下

虽然用了被嘲讽的已经死掉的SPFA，但是其实我觉得SPFA没那么好卡

---

思路

代码

#include<bits/stdc++.h>

using namespace std;

long long h,x,y,z;
long long d[5];
queue<long long> q;
long long dis[100005];
bool vis[100005];

void spfa()
{
	memset(dis,0x3f,sizeof dis);
	memset(vis,0,sizeof vis);
	
	q.push(1);
	dis[1]=1;
	vis[1]=1;
	
	while(!q.empty())
	{
		long long x=q.front();
		q.pop();
		for(long long i=2;i<=3;i++)
		{
			long long y=(x+d[i])%d[1];
			if(dis[y]>dis[x]+d[i])
			{
				dis[y]=dis[x]+d[i];
				if(!vis[y])
				{
					vis[y]=1;
					q.push(y);
				}
			}
		}
		vis[x]=0;
	}
}

long long query(long long x)
{
	long long ans=0;
	for(long long i=0;i<d[1];i++)
	{
		if(x>=dis[i])
		{
			ans+=(x-dis[i])/d[1]+1;
		}
	}
	return ans;
}

int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0),cout.tie(0);

	cin>>h>>d[1]>>d[2]>>d[3];
	sort(d+1,d+4);
	if(d[1]==1||d[2]==1||d[3]==1)
	{
		cout<<h<<"\n";
		return 0;
	}
	
	spfa();
	
	cout<<query(h)<<"\n";

	return 0;
}

---

Finished…