提交时间:2024-10-04 14:47:02
运行 ID: 33120
#include<bits/stdc++.h> using namespace std; long long n,T,b[100005],x,y; long long dis[100005],vis[100005],nmin; struct sss{ long long v,w; }; queue<long long>q; void spfa(){ dis[x]=0,vis[x]=1,q.push(x); while(!q.empty()){ long long now=q.front(); q.pop(),vis[now]=0; if(now<=y)nmin=min(nmin,dis[now]); for(int i=1;i<=n;i++){ long long nv=now/i; if(dis[nv]>dis[now]+b[i]){ dis[nv]=dis[now]+b[i]; if(nv<=y)nmin=min(nmin,dis[nv]); if(vis[nv]==0){ vis[nv]=1; q.push(nv); } } } if(now<=y)nmin=min(nmin,dis[now]); } } int main(){ scanf("%lld%lld",&n,&T); for(int i=1;i<=n;i++){ scanf("%lld",&b[i]); } while(T--){ nmin=0x3f3f3f3f3f3f3f3f; scanf("%lld%lld",&x,&y); for(int i=0;i<=100000;i++){ dis[i]=0x3f3f3f3f3f3f3f3f; } while(!q.empty())q.pop(); if(x<=y){ printf("0\n"); continue; } spfa(); printf("%lld\n",nmin); } }