牛客网算法题（优先队列）

系统管理员 2022-05-28 06:28 178阅读 0赞

链接： [https://www.nowcoder.com/acm/contest/79/E][https_www.nowcoder.com_acm_contest_79_E]  
来源：牛客网

## 题目描述 ##

小欧在上代数课的时候，老师向大家提出了一个问题，不定方程 ax+by=c 的整数解存在的充要条件是什么。  
聪明的小欧立即举手给出了老师一个完美的回答,放学后，老师叫住小欧给了他一个思考题。  
给出正整数 a 和 b 的值以及两个序列 S 和 V, 求出最小代价的正整数 c 使得不定方程 ax+by=c 有解，且 c 必须满足以下条件：  
1. 组成 c 的数字必须是序列 S 内的。  
2. 每使用序列 S 内的一个数字 S i 就会消耗掉代价 V i。  
3. 序列 S 内的数字使用次数不限。  
4. c 的首位为 u， c的末位为 v。(u，v 也是序列 S 内的)  
如果有多个代价一样小的答案，只需要 c 的字典序最小的那一个。

## 输入描述: ##

第一行三个个整数 a，b，n (1 <= a, b <= 100000,  2 <= n <= 10) 
    第二行 n 个整数 Si (0 <= Si <= 9) 
    第三行 n 个整数 Vi (1 <= Vi <= 1000) 
    最后一行两个整数 u，v(1 <= u <= 9,  0 <= v <= 9, u != v)

## 输出描述: ##

输出一行表示满足条件的 c 。
    如果有多个输出字典序最小的。
    如果不存在输出 -1 。

示例1

## 输入 ##

10 15 2
    2 0
    1 1
    2 0

## 输出 ##

示例2

## 输入 ##

17 17 4
    0 1 2 7
    1 1 1 1000
    1 0

## 输出 ##

1020

//分析：首先定义三个数组，数组是跟a，b相关的

//ax+by=c式子有解，则c%gcd(a,b)==0

//最重要的是优先队列思想

代码：

#include<bits/stdc++.h>
    using namespace std;
    #define ll long long
    #define INF 1000000
    struct node
    {
        int s,v;
        bool operator <(const node &a)const
        {
            return a.v<v;
        }
    };
    int V[15],dis[100005],pre[100005],num[100005];
    int p,v,u;
    void print(int x)
    {
        if(pre[x]==-1)
        {
            cout<<u;
            return ;
        }
        print(pre[x]);
        cout<<num[x];
    }
    int bfs(int x)
    {
        memset(dis,INF,sizeof dis);
        dis[x]=0;
        pre[x]=-1;
        priority_queue<node>que;
        que.push({x,0});
        while(!que.empty())
        {
            node tem=que.top();
            que.pop();
            if((tem.s*10+v)%p==0)
            {
                print(tem.s);
                cout<<v<<endl;
                return 1;
            }
            for(int i=0;i<10;i++)
                if(V[i])
            {
                int ns=(tem.s*10+i)%p;
                if(dis[ns]>dis[tem.s]+V[i])
                {
                    dis[ns]=dis[tem.s]+V[i];
                    pre[ns]=tem.s;
                    num[ns]=i;
                    que.push({ns,dis[ns]});
                }
            }
        }
        return 0;
    }
    int main()
    {
        int a,b,n;
        cin>>a>>b>>n;
        p=__gcd(a,b);
        int w[12];
        for(int i=0;i<n;i++)
        {
           cin>>w[i];
        }
        for(int i=0;i<n;i++)
            cin>>V[w[i]];
     
        cin>>u>>v;
        if(bfs(u%p)==0)cout<<-1<<endl;
    }

[https_www.nowcoder.com_acm_contest_79_E]: https://www.nowcoder.com/acm/contest/79/E