首页 > 代码库 > 【最短路】CDOJ1633 去年春恨却来时，落花人独立，微雨燕双飞
【最短路】CDOJ1633 去年春恨却来时，落花人独立，微雨燕双飞
对于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;
}
【最短路】CDOJ1633 去年春恨却来时，落花人独立，微雨燕双飞
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。