【BZOJ 2118】 墨墨的等式（Dijkstra）

BZOJ2118 墨墨的等式

Description

Input

Output

Sample Input

Sample Output

HINT

题解

1. x可以写成k*a[0]+i,(0<=i<a[0])
2. 所以最多只有i个解，我们只需求出每个解的最小代价即可
   
   因此可以建图，每个i与(a[j]+i)%a[0],之间的代价为a[j],之后再求0到每个i之间的距离即可

参考代码

#include <queue>

#include <cmath>

#include <cstdio>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

#include <vector>

#define ll long long

#define inf 10000000000000

#define mod 1000000007

using namespace std;

ll read()

{

    ll x=0,f=1;

    char ch=getchar();

    while(ch<'0'||ch>'9')

    {

        if(ch=='-')f=-1;

        ch=getchar();

    }

    while(ch>='0'&&ch<='9')

    {

        x=x*10+ch-'0';

        ch=getchar();

    }

    return x*f;

}

const int N=5e5+10;

const int M=5e6+10;

int cnt;

struct Edge{

    int cost,to,nxt;

    Edge(){};

    Edge(int tc,int tt,int tn=0):cost(tc),to(tt),nxt(tn){}

    bool operator < (const Edge &an) const{

        return cost>an.cost;

    }

}Path[M];

int a[20],head[N];

ll dis[N];

bool vis[N];

void Addedge(int u,int v,int w){

	Path[cnt]=(Edge){w,v,head[u]};

	head[u]=cnt++;

}

void Dijkstra()

{

    priority_queue<Edge>que;

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

	dis[0]=0;

	que.push(Edge(0,0));

	while(!que.empty()){

		int cur=que.top().to;que.pop();

		if(vis[cur])continue;

		vis[cur]=true;

		for(int i=head[cur];i;i=Path[i].nxt)

			if(dis[cur]+Path[i].cost<dis[Path[i].to]){

				dis[Path[i].to]=dis[cur]+Path[i].cost;

				que.push(Edge(dis[Path[i].to],Path[i].to));

			}

	}

}

ll query(ll x)

{

    ll ans=0;

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

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

    return ans;

}

void Init(){

    cnt=1;

    memset(head,0,sizeof(head));

}

int main(){

    int top=0,n=read();

    ll l=read(),r=read();

    Init();

    for(int i=0;i<n;i++){

         int x=read();

         if(x==0) continue;

         a[top++]=x;

    }

    sort(a,a+top);

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

        for(int j=1;j<top;j++){

             Addedge(i,(a[j]+i)%a[0],a[j]);

        }

    }

    Dijkstra();

    printf("%lld\n",query(r)-query(l-1));

    return 0;

}