同余最短路

  • 题目一般风格:
    图片说明

  • 原题目网址:https://www.luogu.com.cn/problem/P2371

  • 模板代码:

    #include <bits/stdc++.h>
    using namespace std;
    #define ll long long
    const int maxn = 5e5+5;
    ll dis[maxn];
    int n;
    ll l , r;
    int a[30];
    bool flag[maxn];
    queue<int> q;
    void spfa()
    {
       for(int i=0;i<a[1];i++)dis[i] = 1e18;
       q.push(0);flag[0] = 1,dis[0] = 0;
       while(q.size())
       {
           int x = q.front();q.pop();flag[x] = 0;
           for(int i=2;i<=n;i++){
               int o = (x+a[i])%a[1];
               if(dis[o] > dis[x] + a[i]){
                   dis[o] = dis[x] + a[i];
                   if(!flag[o])
                       q.push(o),flag[o] = 1;
               }
           }
       }
    }
    int main()
    {
       scanf("%d%lld%lld",&n,&l,&r);
       for(int i=1;i<=n;i++)
           scanf("%d",&a[i]);
       sort(a+1,a+1+n);
       spfa();
       ll ans = 0;
       for(int i=0;i<a[1];i++){
           if(dis[i] <= r){
               if(dis[i] >= l)
                   ans += ((r-dis[i])/a[1]+1);
               else{
                   ans += ((r-dis[i])/a[1]+1);
                   ans -= (l-dis[i]+a[1]-1)/a[1];
               }
           }
       }
       printf("%lld\n",ans);
    
       return 0;
    }
    

```

acm菜鸡日常 文章被收录于专栏

一般写一些打过的比赛题解以及不会的算法

全部评论

相关推荐

炫哥_:哥们项目描述里面vector和mysql之类的都要写吗,直接开头技术栈巴拉巴拉就行了,完全不是技术点啊
点赞 评论 收藏
分享
自由水:笑死了,敢这么面试不敢让别人说
点赞 评论 收藏
分享
评论
1
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务