前四个AC了,后面全RE。
查看原帖
前四个AC了,后面全RE。
615236
FF_pigeon楼主2023/7/10 14:02

求大佬帮忙看看

#include<bits/stdc++.h>
using namespace std; 
const int N=15,M=6000000+100;
long long a[N];
struct edge
{
    int to,w,next;
}e[M];
long long head[N],dis[N],cnt,m;
bool vis[N];
long long n,l,r,minx=9e18;
inline void add(int u,int v,int w)
{
    cnt++;
    e[cnt].w=w;
    e[cnt].to=v;
    e[cnt].next=head[u];
    head[u]=cnt;
}
void SPFA(int s)
{
	for(int i=0;i<minx;i++)dis[i]=1e12+1;
	queue<int>q;
	dis[s]=0;
	q.push(s);
	while(!q.empty())
	{
		int u=q.front();
        q.pop();
        vis[u]=0;
        for(int v,w,i=head[u];v=e[i].to,w=e[i].w,i;i=e[i].next)
        {
            if(dis[v]>dis[u]+w) 
			{
                dis[v]=dis[u]+w;
                if (!vis[v]) 
				{
                    q.push(v);
                    vis[v]=1;
                }
            }
		}
	}
}
long long qurey(long long k)
{
	long long result=0;
	for(int i=0;i<minx;i++)
	{
		if(dis[i]<=k)
		{
			result+=(k-dis[i])/minx+1;
		}
	}
	return result;
}
int main()
{
	for(int i=0;i<n;i++)dis[i]=9e18;
	cin >> n >> l >> r;
    for(int i=1;i<=n;i++)
    {
    	long long x;
    	cin >> x;
    	a[++m]=x;
		minx=min(x,minx);	
	}
	n=m;
	for(int i=0;i<minx;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(a[j]!=minx)
			{
				add(i,(i+a[j])%minx,a[j]);
			}
		}
	}
	SPFA(0);
	long long ans=qurey(r)-qurey(l-1);
	cout << ans << endl;
    return 0;
}
2023/7/10 14:02
加载中...