题解洛谷P3403 跳楼机

算法：同余最短路。

同余最短路，并不是用同余来跑最短路，而是通过同余来构造某些状态，从而达到优化时间空间复杂度的目的。往往这些状态就是最短路中的点，可以类比差分约束跑最短路(

建边方式
adde(u = i, v = ( i + a ) % b, w = a);

统计答案
for ( i = 0; i < y; ++i) if (h >= dis[i]) ans += (h - dis[i]) / b + 1;

如果要单独讨论

 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<queue>
 4 #define it register int
 5 #define il inline 
 6 using namespace std;
 7 typedef long long ll;
 8 const int N=1000005;
 9 int h[N],nxt[N],adj[N],t;
10 ll d[N],w[N],ans,x,y,z,n;
11 bool inq[N];
12 queue<int> q;
13 il void add(it u,it v,it x){
14     nxt[++t]=h[u],h[u]=t,adj[t]=v,w[t]=x;
15 }
16 il void spfa(){
17     memset(d,0x3f3f3f3f,sizeof(d));
18     d[1]=1,q.push(1);
19     while(!q.empty()){
20         it top=q.front();q.pop();
21         for(it i=h[top];~i;i=nxt[i])
22             if(d[adj[i]]>d[top]+w[i]){
23                 d[adj[i]]=d[top]+w[i];
24                 if(!inq[adj[i]]) inq[adj[i]]=true,q.push(adj[i]);
25             }
26         inq[top]=false;
27     }
28 }
29 il void fr(ll &num){
30     num=0;char c=getchar();int p=1;
31     while(c<'0'||c>'9') c=='-'?p=-1,c=getchar():c=getchar();
32     while(c>='0'&&c<='9') num=num*10+c-'0',c=getchar();
33     num*=p;
34 }    
35 int main(){ 
36     memset(h,-1,sizeof(h));
37     fr(n),fr(x),fr(y),fr(z);
38     for(it i=0;i<z;++i) add(i,(i+x)%z,x),add(i,(i+y)%z,y);
39     spfa();
40     for(it i=0;i<z;++i)
41         if(n>=d[i]) ans+=(n-d[i])/z+1;
42     printf("%lld",ans);
43     return 0;
44 }

View Code