周赛 厂里吃鸡王 题解（多起点bfs）

周赛 厂里吃鸡王 题解（多起点bfs）

题目链接

题目大意

有n个城市，m条路也就是双向边（边可能重复和自环），每个城市都会生产1种装备（不同城市之间的装备可能相同）共有k种不同的装备

每种装备都需要小姐姐送过来。求每一个城市获得k种装备的最短路

题目思路

装备最多100种，可以计算每种装备到每个城镇的最短路。直接将所有生产i型商品的城市一次性全加入队列。

然后bfs最多100次bfs即可。满足题目要求

易错警示

1：双向边一定要记得开两倍

2：vis数组的一二维写反了（找了一年bug

代码

#include<cstdio>
#include<queue>
using namespace std;
const int maxn=5e4+5;
int n,m,k,equip,v,u,cnt,head[maxn],dis[maxn];
bool vis[105][maxn];
queue<pair<int,int> > a[105];
struct node{int to,next;
}e[maxn<<1];
void add(int u,int v){//链式前向星建图e[++cnt].to=v;e[cnt].next=head[u];head[u]=cnt;
}
void bfs(int equip){while(!a[equip].empty()){int pos=a[equip].front().first;//位置int y=a[equip].front().second;//距离a[equip].pop();for(int i=head[pos];i;i=e[i].next){int x=e[i].to;if(!vis[equip][x]){//没有走过则压入队列vis[equip][x]=1;dis[x]=dis[x]+y+1;a[equip].push({x,y+1});}}}
}
int main(){scanf("%d%d%d",&n,&m,&k);for(int i=1;i<=n;i++){scanf("%d",&equip);a[equip].push({i,0});//压入不同种类的队列vis[equip][i]=1;//标记走过}for(int i=1;i<=m;i++){scanf("%d%d",&u,&v);add(u,v),add(v,u);}for(int i=1;i<=k;i++){//对种类进行bfsbfs(i);}for(int i=1;i<=n;i++){for(int j=1;j<=k;j++){if(!vis[j][i]){//没有收集完k种装备dis[i]=0;break;}}if(i<n){printf("%d ",dis[i]);}else{printf("%dn",dis[i]);}}return 0;
}