从差分约束到同余最短路

jzl_1210 · 2026-08-20 22:24:17 · 算法·理论

以前总听说过这个算法，终于可以学一学了。 :::info[AI 使用说明] 使用 AI 进行了部分文本修缮。 :::

算法解决的问题（差分约束部分）

先讲差分约束，差分约束主要是解决形如 x_i - x_j \le k 这样的不等式的算法，当然这个不等式有多个，简单的暴力显然是解决不了这样的问题，所以还要另辟蹊径。

算法解决步骤

用这些不等式可以做什么？我们考虑给他们变形一下，得到 x_i \le x_j + k，而这个东西很像我们熟知的最短路的三角不等式，于是可以拿他搞事情。 :::info[什么是最短路三角不等式] 对于我这个蒟蒻来说，解释这个是十分有必要的。

我们看一下这一张图片，从 s 出发，d_i 表示到达 i 点的最短路，那么显然到达 v 点的最短路有可能是先到达 u，再走边权为 w(u,v) 的边到达点 v，或者走其他的路径，所以就出现了一个不等式 d_v \le d_u + w(u,v)。 ::: 所以说，我们如果把 x_i 和 x_j 分别当做到达 i 和 j 点的最短路，把 k 当做这两个点之间的边权，那么跑最短路，他是不是就自动满足了这个不等式？

答案是肯定的，但我们还要注意一下这条边的方向，一定是 j \rightarrow i，边权为 k。千万不要弄错了。
不难发现，图是不一定连通的，所以应当设置一个超级源点向每个点都连一条边，边权随意。

接下来就需要选择合适的最短路算法，对于这一块，我们需要根据题面合理分析，如果出现负权边，就应当使用 spfa，否则可以使用 dijkstra，毕竟他跑得更快嘛。

还有一个问题，出现负环怎么办，我们看一下如下的图：

从中可以列出不等式组：

\begin{cases} x_1 \le x_3 + 4\\ x_2 \le x_1 + 5\\ x_3 \le x_2 - 11 \end{cases}

我们把这些不等式转化一下，得到 x_2 \le x_2 - 2。这显然是不可能的，所以我们得到结论：当出现负环时，不等式组无解。

当然题目一般来说不会简单的给你形如 x_i - x_j \le k 的不等式，所以需要我们合理转化，具体的：

对于 x_i - x_j \ge k 的不等式，我们在两边同乘 -1，得到 x_j - x_i \le -k。
对于 x_i - x_j = k 的不等式，应当给他拆成两部分，即 x_i - x_j \le k 和 x_i - x_j \ge k。
对于给出一段区间和，我们可以用前缀和数组，定义 q_i 表示前 i 个数的和，那么 q_r - q_{l-1} = k，然后再用第二种方法拆分。

这三种技巧在后续的题目也会经常用到，所以还是要记牢。

算法代码

一般来说都是要使用 spfa 的，我们使用 SLF+LLL 优化，但是码量会更多，因为 LLL 优化比较难写，之后的题目我就只用 SLF 优化了。下面是时间对比（怎么这么糊，将就看吧）：

可以发现其实差别不大。 :::success[朴素 spfa 代码]

#include <bits/stdc++.h>
#define ll long long
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
using namespace std;
const int N = 5e3 + 5, inf = 1e9;
int n, m, vis[N], dis[N], sz[N];
struct node{int to, w;};
vector <node> ed[N];
bool spfa(){//这部分几乎是板子 
    queue <int> q;
    for(int i = 1;i <= n + 1;i++) dis[i] = inf;
    vis[n + 1] = 1, dis[n + 1] = 0, q.push(n + 1);
    while(!q.empty()){
        int now = q.front();
        q.pop(); vis[now] = 0;
        for(auto bl : ed[now]){
            int i = bl.to, bw = bl.w;
            if(dis[now] + bw < dis[i]){
                dis[i] = dis[now] + bw; sz[i] = sz[now] + 1;
                //注意一共 n+1 个点所以判断条件是 sz[i] > n 
                if(sz[i] > n) return 0; if(vis[i]) continue;
                vis[i] = 1, q.push(i);
            }
        }
    }
    return 1;
}
int main(){
    cin >> n >> m;
    //建立超级源点 
    for(int i = 1;i <= n;i++) ed[n + 1].pub({i, 0});
    for(int i = 1;i <= m;i++){
        //建边 
        int u, v, w; cin >> u >> v >> w;
        ed[v].pub({u, w});
    }
    if(!spfa()) return cout << "NO", 0;
    for(int i = 1;i <= n;i++) cout << dis[i] << " ";
    return 0;
}

::: :::success[SLF+LLL 优化代码]

#include <bits/stdc++.h>
#define ll long long
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
using namespace std;
const int N = 5e3 + 5, inf = 1e9;
int n, m, vis[N], dis[N], sz[N];
struct node{int to, w;};
vector <node> ed[N];
bool spfa(){
    deque <int> q;
    for(int i = 1;i <= n + 1;i++) dis[i] = inf;
    vis[n + 1] = 1, dis[n + 1] = 0, q.puf(n + 1);
    int cnt = 1; ll sum = dis[n + 1];
    while(!q.empty()){
        int now = q.front();
        //LLL优化 
        while(1ll * dis[now] * cnt > sum) q.pof(), q.pub(now), now = q.front();
        q.pof(); vis[now] = 0, cnt--, sum -= dis[now];
        for(auto bl : ed[now]){
            int i = bl.to, bw = bl.w;
            if(dis[now] + bw < dis[i]){
                dis[i] = dis[now] + bw; sz[i] = sz[now] + 1;
                if(sz[i] > n) return 0; if(vis[i]) continue;
                vis[i] = 1, cnt++, sum += dis[i];
                //SLF优化 
                if(q.empty() || dis[i] < dis[q.front()]) q.puf(i);
                else q.pub(i);
            }
        }
    }
    return 1;
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++) ed[n + 1].pub({i, 0});
    for(int i = 1;i <= m;i++){
        int u, v, w; cin >> u >> v >> w;
        ed[v].pub({u, w});
    }
    if(!spfa()) return cout << "NO", 0;
    for(int i = 1;i <= n;i++) cout << dis[i] << " ";
    return 0;
}

:::

例题

P1993 小 K 的农场

这道题几乎也是板子，只需要根据那 3 点合理转化就行。 :::success[code]

#include <bits/stdc++.h>
#define ll long long
#define puf push_front
#define pof pop_front
#define pub push_back
#define pob pop_back
using namespace std;
const int N = 5e3 + 5, inf = 1e9;
int n, m, vis[N], dis[N], sz[N];
struct node{int to, w;};
vector <node> ed[N];
bool spfa(){
    deque <int> q;
    for(int i = 1;i <= n + 1;i++) dis[i] = inf;
    vis[n + 1] = 1, dis[n + 1] = 0, q.puf(n + 1);
    while(!q.empty()){
        int now = q.front();
        q.pof(); vis[now] = 0;
        for(auto bl : ed[now]){
            int i = bl.to, bw = bl.w;
            if(dis[now] + bw < dis[i]){
                dis[i] = dis[now] + bw; sz[i] = sz[now] + 1;
                if(sz[i] > n) return 0; if(vis[i]) continue;
                vis[i] = 1;
                if(q.empty() || dis[i] < dis[q.front()]) q.puf(i);
                else q.pub(i);
            }
        }
    }
    return 1;
}
int main(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++) ed[n + 1].pub({i, 0});
    for(int i = 1;i <= m;i++){
        int op, u, v, w; cin >> op;
        if(op == 1) cin >> u >> v >> w, ed[u].pub({v, -w});
        if(op == 2) cin >> u >> v >> w, ed[v].pub({u, w});
        if(op == 3) cin >> u >> v, ed[u].pub({v, 0}), ed[v].pub({u, 0});
    }
    cout << (spfa() ? "Yes" : "No");
    return 0;
}

:::

P2294 [HNOI2005] 狡猾的商人

这一道题目也几乎是板子，把区间和转化成前缀和相减就可以了，还是很简单的，这里不过多赘述。
这时候可能有人会问了，定义 q_i 为前 i 个数的和，这样子直接差分约束不保证 q_0=0 怎么办。其实如果 \{ x_1,x_2,\dots,x_n \} 是不等式的一组解，那么 \{ x_1+k,x_2+k,\dots,x_n+k \} 也是不等式的解，其中 k 为任意实数，因为这样子消掉后可以满足条件。因此，只要同时加减常数就能让 q_0=0 了，前提是有解的情况下。 :::success[code]

#include <bits/stdc++.h>
#define ll long long
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
using namespace std;
const int N = 105, inf = 1e9;
int n, m, T, dis[N], vis[N], sz[N];
struct node{int to, w;};
vector <node> ed[N];
bool spfa(){
    deque <int> q;
    for(int i = 0;i <= n + 1;i++) dis[i] = inf;
    vis[n + 1] = 1, dis[n + 1] = 0, q.puf(n + 1);
    while(!q.empty()){
        int now = q.front();
        q.pof(), vis[now] = 0;
        for(auto bl : ed[now]){
            int i = bl.to, bw = bl.w;
            if(dis[now] + bw < dis[i]){
                dis[i] = dis[now] + bw, sz[i] = sz[now] + 1;
                if(sz[i] > n + 1) return 0;//此时有 n+2 个点最多执行 n+1 轮 
                if(vis[i]) continue;
                vis[i] = 1;
                //注意，一定要判队列是否为空，否则 RE 找上门 
                if(!q.empty() && dis[i] < dis[q.front()]) q.puf(i);
                else q.pub(i);
            }
        }
    }
    return 1;
}
int main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> T;
    while(T--){
        cin >> n >> m;
        for(int i = 0;i <= n;i++) ed[n + 1].pub({i, 0});
        for(int i = 1;i <= m;i++){
            int s, t, w; cin >> s >> t >> w;
            ed[s - 1].pub({t, w}), ed[t].pub({s - 1, -w});
        }
        cout << (spfa() ? "true" : "false") << "\n";
        for(int i = 0;i <= n + 1;i++) ed[i].clear(), vis[i] = sz[i] = 0;
    }
    return 0;
}

:::

P4878 [USACO05DEC] Layout G

这一道题目看似是板子，但是它有坑！设 a_i 表示奶牛 i 的位置，那么根据题意可以得到 a_r - a_l \le k 和 a_r - a_l \ge k。但是只有这些吗？我们要注意题目里的隐藏条件，看到题面里的一句话：奶牛们始终需要按照编号顺序来排队。这就代表着 i 更大的奶牛一定在 i 更小的奶牛后面，换成代数语言就是 a_i - a_{ i - 1} \ge 0。这就得到了重要的不等式。

接下来考虑 1 号和 N 号之间的最大距离怎么求。这样想，如果从 s 到 t 有 m 条路可以到达，长度分别为 d_1,d_2, \dots d_m 我们选择哪一条？变成不等式看看：

\begin{cases} a_t \le a_s + d_1\\ a_t \le a_s + d_2\\ \vdots\\ a_t \le a_s + d_m \end{cases}

这样看是不是显而易见？我们应该选择长度最短的那一条才能满足所有不等式。于是解法就出来了！从 1 开始走到 n 查最短路，如果没有路就说明两点距离可以无穷大。由此我们也可以知道，最短路求的是答案的上界。 :::success[code]

#include <bits/stdc++.h>
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
using namespace std;
const int N = 1005, inf = 1e9;
int n, T1, T2, dis[N], vis[N], sz[N];
struct node{ int to, w; };
vector <node> ed[N];
bool spfa(int s, int l, int r){//spfa板子 
    deque <int> q;
    for(int i = l;i <= r;i++) dis[i] = inf, vis[i] = sz[i] = 0;
    dis[s] = 0, q.puf(s), vis[s] = 1;
    while(!q.empty()){
        int now = q.front();
        q.pof(), vis[now] = 0;
        for(auto bl : ed[now]){
            int i = bl.to, bw = bl.w;
            if(dis[now] + bw < dis[i]){
                dis[i] = dis[now] + bw;
                sz[i] = sz[now] + 1;
                if(sz[i] >= (r - l + 1)) return 0;
                if(vis[i]) continue;
                vis[i] = 1;
                if(q.empty() || dis[i] < dis[q.front()]) q.puf(i);
                else q.pub(i);
            }
        } 
    }
    return 1;
}
int main(){
    cin >> n >> T1 >> T2;
    for(int i = 1;i <= n;i++) ed[n + 1].pub({i, 0});
    for(int i = 2;i <= n;i++) ed[i].pub({i - 1, 0});//注意这部分建边 
    while(T1--){//第一组关系 
        int l, r, w; cin >> l >> r >> w;
        ed[l].pub({r, w});
    }
    while(T2--){//第二组关系 
        int l, r, w; cin >> l >> r >> w;
        ed[r].pub({l, -w});
    }
    //简单的判断 
    if(!spfa(n + 1, 1, n + 1)) return cout << "-1", 0;
    spfa(1, 1, n);
    cout << (dis[n] == inf ? -2 : dis[n]);
    return 0;
}

:::

P3275 [SCOI2011] 糖果

注意，这一道题目并不能用 spfa 拿到满分，不过也是一道不错的练手题。
上一题说到了最短路其实是求答案的上界，那么这一题要求下界就应该使用最长路，具体来说就是把题目给的信息转化成不等式，实现起来不难，唯一要注意的地方是每个小朋友都要分到糖果这句话，对于这种条件，我们可以建立超级源点，向每个点连一条边权为 1 的边，这样子这些点的最长路都至少是 1，也就满足了条件。

:::warning[注意这份代码非正解]

#include <bits/stdc++.h>
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
#define int long long
using namespace std;
const int N = 1e5 + 5, inf = 1e9;
int n, k, dis[N], sz[N]; bool vis[N];
struct node{ int to, w; };
vector <node> ed[N];
bool spfa(){//简单的spfa 
    deque <int> q;
    for(int i = 1;i <= n + 1;i++) dis[i] = -inf;
    dis[n + 1] = 0, q.puf(n + 1), vis[n + 1] = 1;
    while(!q.empty()){
        int now = q.front();
        q.pof(); vis[now] = 0;
        for(auto bl : ed[now]){
            int i = bl.to, bw = bl.w;
            if(dis[now] + bw > dis[i]){
                dis[i] = dis[now] + bw; sz[i] = sz[now] + 1;
                if(sz[i] >= n + 1) return 0; if(vis[i]) continue;
                vis[i] = 1;
                if(q.empty() || dis[i] < dis[q.front()]) q.puf(i);
                else q.pub(i);
            }
        }
    }
    return 1;
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k;
    //简单的建边 
    for(int i = 1;i <= n;i++) ed[n + 1].pub({i, 1});
    for(int i = 1;i <= k;i++){
        int bh, u, v; cin >> bh >> u >> v;
        if(bh == 1) ed[v].pub({u, 0}), ed[u].pub({v, 0});
        if(bh == 2) ed[u].pub({v, 1});
        if(bh == 3) ed[v].pub({u, 0});
        if(bh == 4) ed[v].pub({u, 1});
        if(bh == 5) ed[u].pub({v, 0});
    }
    if(!spfa()) return cout << -1, 0;
    int ans = 0;
    for(int i = 1;i <= n;i++) ans += dis[i];
    cout << ans;
    return 0;
}

::: 接下来讲讲这题正解怎么做，我们注意到本题的边权只有 0 和 1，并没有负权边，所以如果有一个强连通分量，那么是不是只要里面有一条边为 1，就会出现正环，此题就无解，否则的话这个强连通分量的所有边都是零。这个时候我们只要考虑两个强连通分量的边就行了。

所以受此启发，这题的正解就是缩点，然后拓扑排序一下求最长路就行了。 :::success[code]

#include <bits/stdc++.h>
#define pub push_back
#define int long long
using namespace std;
const int N = 1e5 + 5, inf = 1e9;
int n, k, tot, top, dp[N], ind[N]; bool pd[N];
int low[N], dfn[N], stk[N], zx[N], siz[N];
struct node{ int to, w; };
vector <node> ed[N], ed2[N]; queue <int> q;
void dfs(int x){//tarjan求强连通分量 
    low[x] = dfn[x] = ++tot;
    stk[++top] = x, pd[x] = 1;
    for(auto bl : ed[x]){
        int i = bl.to;
        if(!dfn[i]){
            dfs(i);
            low[x] = min(low[x], low[i]);
        } else if(pd[i])
            low[x] = min(low[x], dfn[i]);
    }
    if(low[x] == dfn[x]){
        while(1){
            int y = stk[top--]; pd[y] = 0;
            zx[y] = x; siz[x]++;
            if(y == x) break;
        }
    }
}
signed main(){
    ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
    cin >> n >> k;
    for(int i = 1;i <= n;i++) ed[n + 1].pub({i, 1});
    for(int i = 1;i <= k;i++){
        int bh, u, v; cin >> bh >> u >> v;
        if(bh == 1) ed[v].pub({u, 0}), ed[u].pub({v, 0});
        if(bh == 2) ed[u].pub({v, 1});
        if(bh == 3) ed[v].pub({u, 0});
        if(bh == 4) ed[v].pub({u, 1});
        if(bh == 5) ed[u].pub({v, 0});
    }
    n++; for(int i = 1;i <= n;i++) if(!dfn[i]) dfs(i);
    for(int i = 1;i <= n;i++){//缩点 
        for(auto bl : ed[i]){
            int j = bl.to, bw = bl.w;
            if(zx[i] == zx[j] && bw == 1)
                return cout << -1, 0;
            int z1 = zx[i], z2 = zx[j];
            if(z1 != z2) ed2[z1].pub({z2, bw}), ind[z2]++;
        }
    }
    for(int i = 1;i <= n;i++) if(zx[i] == i && ind[i] == 0) q.push(i);
    //拓扑排序 
    while(!q.empty()){
        int t = q.front(); q.pop();
        for(auto bl : ed2[t]){
            int i = bl.to, bw = bl.w;
            dp[i] = max(dp[i], dp[t] + bw);
            if(--ind[i] == 0) q.push(i);
        }
    }
    int ans = 0;
    for(int i = 1;i <= n;i++) 
        ans += dp[zx[i]];
    cout << ans;
    return 0;
}

:::

算法解决的问题（同余最短路部分）

可以看这道题的题面，这是同余最短路的标准形式，这里我把它放出来。

求解这个方程：\sum_{i=1}^{n} a_i x_i = b，其中 a 数组是给定的。然后再给出两个整数 l,r，求有多少 b \in [l,r] 使得这个方程存在非负整数解。

算法解决步骤

我们先从简化版的题目跳楼机讲起，即求有多少个整数 d \in [0,h-1] 满足 ax+by+cz=d，其中 a,b,c 都为非负整数，而 x,y,z 是给定的。

我们可以这样想，如果一个数满足了 d=by+cz，那么 d,d+x,d+2x \cdots 都是满足条件的解，所以我们可以把原始变形一下，即同时对 x 取余，变成 by + cz = d \bmod x。那么答案就是 (by + cz) \bmod x + k \cdot x，其中 k 应为非负整数。

这样做有什么好处？这也是我初次看题解不太理解的地方，我们这样想，如果按照原式 ax + by + cz = d，我们会发现如果枚举 a,b,c 结果 d 多多少少会有重复的，这样就会导致答案很难计算，我们看变形后的答案式子，只要枚举余数，那么就可以得到对于这个余数的所有答案，且可以满足不重不漏，更重要的是，我们可以构造出不等式，再用类似差分约束的办法解决，这样复杂度也得到了保证。

所以可以从中受到启发，定义 f_i 表示满足 (by+cz) \bmod x = i 时最小的 by+cz。 :::info[为什么一定要是最小的] 考虑到有人肯定知道，但是为了解释的更清楚，我就放折叠框里了。
我们考虑到结果 d 是不是应该在 [0,h-1] 内，所以让 by+cz 最小，才能加更多的 x，这样才能保证不漏掉某些答案。 ::: 接下来就是最重要的两个不等式：

f_{(i + y) \bmod x} \le f_i + y \\ f_{(i + z) \bmod x} \le f_i + z

其实这两个不等式也很好理解，显然 f_i + y 就可以用来更新 f_{(i+y) \bmod x} 换言之它们两个式子之间是包含的关系，所以要么相等，要么 f_{(i+y) \bmod x} 更小，否则它可以被更新。

得到了不等式，接下来就可以用类似差分约束的办法解决。显然 f_0=0，所以源点直接设为 0 即可。接下来考虑答案怎么计算，对于某个余数的 f_i，如果它不超过 h-1，这部分的贡献就是 \lfloor \frac{h-1-f_i}{x} \rfloor + 1，因为剩下的间隔里每 x 个就是一个贡献。那么答案就是：

\sum_{i=0}^{x-1} (\lfloor \frac{h-1-f_i}{x} \rfloor + 1)

算法代码

不难发现，这一块没有负权边，所以可以使用 dijkstra 算法求解，这里给出 P3403 的代码。 :::success[code]

#include <bits/stdc++.h>
#define int long long
#define pub push_back
using namespace std;
const int N = 1e5 + 5, inf = 1e18;
int h, x, y, z, dis[N];
bool vis[N];
struct node{int to, w;};
vector <node> ed[N];
bool operator < (node t1, node t2){ return t1.w > t2.w; }
void dij(){ //朴实无华的 dijkstra 
    priority_queue <node> q;
    memset(vis, 0, sizeof vis);
    for(int i = 0;i < x;i++) dis[i] = inf;
    dis[0] = 0, q.push({0, 0});
    while(!q.empty()){
        int now = q.top().to;
        q.pop(); if(vis[now]) continue;
        vis[now] = 1;
        for(auto bl : ed[now]){
            int i = bl.to, bw = bl.w;
            if(dis[now] + bw < dis[i])
                dis[i] = dis[now] + bw, 
                q.push({i, dis[i]});
        }
    }
}
int calc(int h){ //计算答案 
    dij(); int ans = 0;
    for(int i = 0;i < x;i++)
        if(dis[i] <= h) ans += (h - dis[i]) / x + 1;
    return ans;
}
signed main(){
    cin >> h >> x >> y >> z;
    for(int i = 0;i < x;i++){ //简单的建边 
        ed[i].pub({(i + y) % x, y});
        ed[i].pub({(i + z) % x, z});
    }
    cout << calc(h - 1);
    return 0;
}

::: 但是我好像发现了一个问题，就是用 spfa 好像更快耶，由于特殊的建边方式，spfa 算法并不会被卡，所以接下来的题目我们就用 spfa 吧。
为了使证据充分，我们以 P2371 [国家集训队] 墨墨的等式这道题为例，看一下时间对比，这一道题也是标准的模板，需要注意的是有两个地方：

注意 a_i = 0 的情况。
模数可以取一个最小且非零的 a_i，这样子可以减小复杂度。

下面是时间对比图片：
:::success[spfa 代码]

#include <bits/stdc++.h>
#define int long long
#define pub push_back
#define pob pop_back
#define puf push_front
#define pof pop_front
using namespace std;
const int N = 15, MAX = 5e5 + 5, inf = 1e12;
int n, m, l, r, a[N], dis[MAX], zx = MAX;
bool vis[MAX];
struct node{int to, w;};
vector <node> ed[MAX];
void spfa(){
    deque <int> q;
    for(int i = 0;i < zx;i++) dis[i] = inf;
    dis[0] = 0, q.puf(0);
    while(!q.empty()){
        int now = q.front();
        q.pof(), vis[now] = 0;
        for(auto bl : ed[now]){
            int i = bl.to, bw = bl.w;
            if(dis[now] + bw < dis[i]){
                dis[i] = dis[now] + bw;
                if(vis[i]) continue; vis[i] = 1;
                if(dis[i] < dis[q.front()]) q.puf(i);
                else q.pub(i);
            }   
        }
    }
}
int calc(int h){
    int ret = 0;
    for(int i = 0;i < zx;i++)
        if(dis[i] <= h) ret += (h - dis[i]) / zx + 1;
    return ret;
}
signed main(){
    cin >> m >> l >> r;
    for(int i = 1;i <= m;i++){
        int x; cin >> x;
        if(x) a[++n] = x, zx = min(zx, x);
    }
    if(n == 0) return cout << 0, 0;
    for(int i = 0;i < zx;i++)
        for(int j = 1;j <= n;j++)
            if(a[j] != zx) ed[i].pub({(i + a[j]) % zx, a[j]});
    spfa(); cout << calc(r) - calc(l - 1);
    return 0;
}

::: :::success[dijkstra 代码]

#include <bits/stdc++.h>
#define int long long
#define pub push_back
using namespace std;
const int N = 15, MAX = 5e5 + 5, inf = 1e12;
int n, m, l, r, a[N], dis[MAX], zx = MAX;
bool vis[MAX];
struct node{int to, w;};
bool operator < (node t1, node t2){ return t1.w > t2.w; }
vector <node> ed[MAX];
void dij(){
    priority_queue <node> q;
    memset(vis, 0, sizeof vis);
    for(int i = 0;i < zx;i++) dis[i] = inf;
    dis[0] = 0, q.push({0, 0});
    while(!q.empty()){
        int now = q.top().to; q.pop();
        if(vis[now]) continue;
        vis[now] = 1;
        for(auto bl : ed[now]){
            int i = bl.to, bw = bl.w;
            if(dis[now] + bw < dis[i])
                dis[i] = dis[now] + bw, 
                q.push({i, dis[i]});
        }
    }
}
int calc(int h){
    int ret = 0;
    for(int i = 0;i < zx;i++)
        if(dis[i] <= h) ret += (h - dis[i]) / zx + 1;
    return ret;
}
signed main(){
    cin >> m >> l >> r;
    for(int i = 1;i <= m;i++){
        int x; cin >> x;
        if(x) a[++n] = x, zx = min(zx, x);
    }
    if(n == 0) return cout << 0, 0;
    for(int i = 0;i < zx;i++)
        for(int j = 1;j <= n;j++)
            if(a[j] != zx) ed[i].pub({(i + a[j]) % zx, a[j]});
    dij(); cout << calc(r) - calc(l - 1);
    return 0;
}

::: 同余最短路的例题不多，以后应该也会更新的。