NC15364. 小欧的烦恼
描述
输入描述
第一行三个个整数 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
C++11(clang++ 3.9) 解法, 执行用时: 59ms, 内存消耗: 1892K, 提交时间: 2018-03-24 07:44:54
#include<bits/stdc++.h>
using namespace std;
#define N 100010
#define M 15
int S[M],V[M],dis[N],Pre[N],cha[N];
bool mark[N];
queue<int>Q;
void output(int x){
if (!~x) return;
output(Pre[x]);
printf("%d",cha[x]);
}
int main(){
int a,b,n,i,u,v;
cin>>a>>b>>n;
int g=__gcd(a,b);
for (i=1;i<=n;i++) cin>>S[i];
for (i=1;i<=n;i++) cin>>V[S[i]];
cin>>u>>v;
memset(dis,63,sizeof(dis));
dis[u%g]=0;
Pre[u%g]=-1;
cha[u%g]=u;
Q.push(u%g);
int Ans=-1;
while (!Q.empty()){
int x=Q.front();Q.pop();
mark[x]=0;
if ((x*10+v)%g==0 && !~Ans) Ans=x;
for (i=0;i<=9;i++){
if (!V[i]) continue;
int to=(x*10+i)%g;
if (dis[to]>dis[x]+V[i]){
dis[to]=dis[x]+V[i];
Pre[to]=x;
cha[to]=i;
if (!mark[to]){
mark[to]=1;
Q.push(to);
}
}
}
}
if (Ans==-1){
printf("-1\n");
}else{
output(Ans);
printf("%d\n",v);
}
return 0;
}