Codeforces 986 A

Codeforces 986 A

​​传送门​​

标签是数论，结果是个最短路，有点点小懵逼。

BFS

题目大意

n个城市，每个城市分别产生一种商品，商品种类一共有k中，问从第i个城市出发至少得到s件商品的最短路径。

思路

对于每一个小镇i，求出到每件物品j的最短距离即可。

代码

int n,m,s,k;int a[maxn];vector e[maxn];int vis[maxn];int step[maxn][120];int main(){ cin>>n>>m>>k>>s; for(int i=1;i<=n;i++){ cin>>a[i]; } int v,u; for(int i=1;i<=m;i++){ cin>>u>>v; e[u].push_back(v); e[v].push_back(u); } for(int i=1;i<=k;i++){ queueq; memset(vis,0,sizeof vis); for(int j=1;j<=n;j++){ if(a[j]==i){ step[j][i]=0; q.push(j); vis[j]=1; } } while(!q.empty()){ int x=q.front(); q.pop(); for(int j=0;j

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。