【BZOJ2118】墨墨的等式（最短路）

题面

BZOJ

洛谷

题解

和跳楼机那题是一样的。

只不过走的方式从\(3\)种变成了\(n\)种而已，其他的根本没有区别了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<queue>

using namespace std;

#define MAX 500500

#define ll long long

inline int read()

{

	int x=0;bool t=false;char ch=getchar();

	while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

	if(ch=='-')t=true,ch=getchar();

	while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

	return t?-x:x;

}

ll B1,B2,dis[MAX],ans;

int n;

int a[MAX],tot;

bool vis[MAX];

void SPFA()

{

	memset(dis,63,sizeof(dis));

	queue<int> Q;Q.push(0);dis[0]=0;vis[0]=true;

	while(!Q.empty())

	{

		int u=Q.front();Q.pop();

		for(int i=2;i<=n;++i)

		{

			int v=(u+a[i])%a[1];

			if(dis[v]>dis[u]+a[i])

			{

				dis[v]=dis[u]+a[i];

				if(!vis[v])vis[v]=true,Q.push(v);

			}

		}

		vis[u]=false;

	}

}

int main()

{

	cin>>n>>B1>>B2;

	for(int i=1;i<=n;++i)if((a[i]=read()))a[++tot]=a[i];

	n=tot;

	for(int i=2;i<=n;++i)if(a[i]<a[1])swap(a[1],a[i]);

	SPFA();

	for(int i=0;i<a[1];++i)

	{

		if(dis[i]<=B2)ans+=(B2-dis[i])/a[1]+1;

		if(dis[i]<=B1-1)ans-=(B1-1-dis[i])/a[1]+1;

	}

	cout<<ans<<endl;

	return 0;

}