还是同余最短路啊，类似跳楼机那道题。
1 #include<cstdio> 2 #include<cstring> 3 #include<algorithm> 4 #include<queue> 5 #define ll long long 6 using namespace std; 7 8 int n,x; 9 ll mx,mn; 10 int hd[500005],to[5500005],nx[5500005],ec; 11 ll len[5500005]; 12 ll dis[500005]; 13 bool vis[500005]; 14 int a[15]; 15 16 void edge(int af,int at,ll el) 17 { 18 to[++ec]=at; 19 nx[ec]=hd[af]; 20 hd[af]=ec; 21 len[ec]=el; 22 } 23 24 struct data 25 { 26 int p; 27 ll d; 28 friend bool operator < (data q,data w) 29 { 30 return q.d>w.d; 31 } 32 }; 33 34 priority_queue<data>qq; 35 36 void dijkstra() 37 { 38 memset(dis,0x3f,sizeof(dis)); 39 dis[0]=0; 40 qq.push((data){0,0}); 41 while(!qq.empty()) 42 { 43 data nw=qq.top(); 44 qq.pop(); 45 if(vis[nw.p])continue; 46 vis[nw.p]=1; 47 for(int i=hd[nw.p];i;i=nx[i]) 48 { 49 if((!vis[to[i]])&&dis[to[i]]>nw.d+len[i]) 50 { 51 dis[to[i]]=nw.d+len[i]; 52 qq.push((data){to[i],dis[to[i]]}); 53 } 54 } 55 } 56 } 57 58 int main() 59 { 60 scanf("%d%lld%lld",&n,&mn,&mx); 61 for(int i=1;i<=n;i++) 62 { 63 scanf("%d",&a[i]); 64 if(!a[i])n--,i--; 65 } 66 x=a[n],mn--; 67 for(int i=1;i<n;i++) 68 { 69 for(int j=0;j<x;j++) 70 edge(j,(j+a[i])%x,(ll)a[i]); 71 } 72 dijkstra(); 73 ll ans1=0,ans2=0; 74 for(int i=0;i<x;i++) 75 { 76 if(dis[i]<=mx)ans1+=(mx-dis[i])/x+1; 77 if(dis[i]<=mn)ans2+=(mn-dis[i])/x+1; 78 } 79 printf("%lld",ans1-ans2); 80 return 0; 81 }