题意

给你一个大小为 \(n\) 的集合 \(S\) ，集合里有 \(n\) 个互不相同正整数，有 \(q\) 个询问，每次询问是否能选择 \(S\) 中的一些数字 ( 同一个数字可以选择多次,也可以任何数字都不选)，使它们相加的和为 \(m\) 。

分析

这种题型 竟然 可以套用最短路的模型。

如果 \(k\) 在集合中，那么如果 \(a\) 是合法的和的方案，那么 \(a + k\) 一定是合法的。

那么我们只要求出 \(\% k\) 后得到 \([0, k - 1]\) 这些数的最小的和（ \(d\) 数组）。那么判断是否可以组成 \(m\) ，只需要 \(m >= d[m \% k]\) 。

主要就是维护一个小的先出的优先队列 ，所以先出来的值 ( 假设是 \(x\) ) \(\% k\) 的相同的余数中一定是最小的，这个时候就要标记 \(vis[x \% k] = 1\) ，所有后面出来的值 \(y\) ，如果 \(vis[y \% k]\) 已经标记过 ( 假设就是前面的 \(x\) 标记的 ) ，可以直接跳过，因为 \(x \% k == y \% k\) ，且 \(x < y\) ，前面 \(x\) 出队列后已经更新了其它的可能出现的余数，在拿 \(y\) 去更新就没必要了。

code

#include
    
     using namespace std;const int MAXN = 2e3 + 10;const int INF = 1e9 + 7;int n, a[MAXN];int d[50005];int vis[50005];void dij(int w) {    priority_queue