对于S集合中的数,例如a1,考虑到如果x能够被表示出来,那么x+a1也一定能被表示出来

设d[r]为所有模a1余r的数中,能被表示出来的最小的数

用d[x]+ai去更新d[(x+ai)%a1],跑最短路即可

不用真的建出图来,因为图是完全的。否则会MLE。

#include<cstdio>
#include<queue>
#include<cstring>
using namespace std;
queue<int>q;
int n,a[2010],m,dis[50010];
bool inq[50010];
void spfa(int s)
{
memset(dis+1,0x7f,sizeof(dis));
q.push(s); inq[s]=1; dis[s]=0;
while(!q.empty())
{
int U=q.front();
for(int i=2;i<=n;++i)
if(dis[(U+a[i])%a[1]]>dis[U]+a[i])
{
dis[(U+a[i])%a[1]]=dis[U]+a[i];
if(!inq[(U+a[i])%a[1]])
{
q.push((U+a[i])%a[1]);
inq[(U+a[i])%a[1]]=1;
}
}
q.pop(); inq[U]=0;
}
}
int main(){
// freopen("b.in","r",stdin);
scanf("%d",&n);
for(int i=1;i<=n;++i){
scanf("%d",&a[i]);
}
spfa(0);
int x;
scanf("%d",&m);
for(int i=1;i<=m;++i){
scanf("%d",&x);
puts(dis[x%a[1]]<=x ? "YES" : "NO");
}
return 0;
}

最新文章

  1. 疯狂JAVA16课之对象与内存控制
  2. UML - 类图
  3. 导出带图形的数据excel表
  4. Sqli-labs less 31
  5. 【jQuery】
  6. Feedly使用技巧
  7. [转]linux下IPTABLES配置详解
  8. 第一次当Uber司机,就拉到漂亮妹纸
  9. 201521123108 《Java程序设计》第13周学习总结
  10. Laravel认证模块开发
  11. LVM管理之减少LV的大小
  12. tomcat和eclipse-wtp的一些配置
  13. npm安装vue
  14. CF1010D Mars rover [位运算,DP]
  15. Opserver 初探二《exceptions配置》
  16. Swift-懒加载使用
  17. eclipse+maven+tomcat构建web工程
  18. DB开发之mysql
  19. selenium+python—实现自动化测试基本思路
  20. C# 委托,事件, 异步

热门文章

  1. jQuery清空表单方法
  2. 3.0docker操作
  3. LCD 每隔10分钟 自动熄灭 --打开Framebuffer console的时候【转】
  4. Oracle with重用子查询
  5. 2015多校第6场 HDU 5361 并查集,最短路
  6. 通过file中的字段查询MySQL内容
  7. plus.networkinfo.getCurrentType()
  8. VMware无法识别USB设备
  9. php设计模式四 ---- 原型模式
  10. 同步方法-java