首页 > 试题广场 >

小欧的烦恼

[编程题]小欧的烦恼
小欧在上代数课的时候，老师向大家提出了一个问题，不定方程 ax+by=c 的整数解存在的充要条件是什么。
聪明的小欧立即举手给出了老师一个完美的回答,放学后，老师叫住小欧给了他一个思考题。
给出正整数 a 和 b 的值以及两个序列 S 和 V, 求出最小代价的正整数 c 使得不定方程 ax+by=c 有解，且 c 必须满足以下条件：
1. 组成 c 的数字必须是序列 S 内的。
2. 每使用序列 S 内的一个数字 Si 就会消耗掉代价 Vi。
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

输出

20
示例2

输入

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

输出

1020
算法知识视频讲解
开通博客
头像 已注销
发表于 2021-10-13 13:58:41
简单易知存在ax+by=(a,b) 故ax'+by'=n,n必为(a,b)倍数 将%(a,b)的余数视为node，从u%(a,b)到0找最短路 dij优先队列维护花费，pre记录前导，num记录node对应的数字 #include<iostream> #include&l 展开全文
去ta的博客 赞 (2) 回复(0) 收起

问题信息

深度优先搜索(DFS) 最短路
上传者：牛客301599号
难度：
0条回答 15浏览

热门推荐

通过挑战的用户

查看代码

相关试题

小欧的烦恼

扫一扫，把题目装进口袋

求职之前，先上牛客

扫描二维码，进入QQ群

扫描二维码，关注牛客公众号