2020牛客暑期多校训练营（第八场）A.All-Star Game

发表于 | 阅读数

同余最短路模版题

代码 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81



#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pii pair<int, int>
#define mk make_pair
const int N = 1e6 + 10;
const int mod = 1e9 + 7;

namespace SPFA
{
    vector<pii> g[N];
    ll dis[N];
    int vis[N];
    void spfa(int s)
    {
        queue<int> q;
        memset(dis, 0x3f3f3f3f, sizeof(dis));
        q.push(s);
        vis[s] = 1;
        dis[s] = 0;
        while (!q.empty())
        {
            int x = q.front();
            q.pop();
            vis[x] = 0;
            for (pii now : g[x])
            {
                int to = now.first;
                int w = now.second;

                if (dis[to] > dis[x] + w)
                {
                    dis[to] = dis[x] + w;
                    if (!vis[to])
                    {
                        q.push(to);
                        vis[to] = 1;
                    }
                }
            }
        }
    }
} // namespace SPFA

using namespace SPFA;
int a[N];
int main()
{
    int n;
    ll l, r;
    scanf("%d%lld%lld", &n, &l, &r);
    for (int i = 1; i <= n; i++)
    {
        scanf("%d", &a[i]);
    }
    sort(1 + a, 1 + a + n);
    for (int i = 0; i < a[1]; i++)
        for (int j = 2; j <= n; j++)
        {
            // cout << i << " " << (i + a[i]) % a[1] << endl;
            g[i].push_back(mk((i + a[j]) % a[1], a[j]));
        }
    spfa(0);
    ll res = 0;
    for (int i = 0; i < a[1]; i++)
    {

        if (dis[i] <= l - 1)
            res -= (l - 1 - dis[i]) / a[1] + 1;
    }
    for (int i = 0; i < a[1]; i++)
    {

        if (dis[i] <= r)
            res += (r - dis[i]) / a[1] + 1;
    }
    cout << res << endl;
}