CodeForces - 987D Fair (BFS求最短路) - JavaScript

提示：扫一扫查出行
【扫一扫了解最新限行尾号】
复制提示

题意：有N个城市，M条双向道路连接两个城市，整个图保证连通。有K种物品，但每个城市只有一种，现在它们都需要S种物品来举办展览，可以去其他城市获取该城市的物品，花费是两城市之间的最短路径长度。求每个城市举办展览的最小花费。

分析：去某个城市获取第i种物品的最小距离，这个问题可以逆向求解。把拥有第i种物品的城市当作源点，BFS求出它们到其他城市的最短路。对K种物品都如此求一遍最短路。

计算结果的时候，排序后贪心地选择花费前S小的物品即可。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int maxn =1e5+;
int a[maxn];
int res[maxn];
vector<int> G[maxn];
bool vis[maxn];
int d[maxn][];
void init(int N) {for(int i=;i<=N;++i) G[i].clear();}
void AddEdge(int u,int v){G[u].push_back(v);}void BFS(int val,int N)
{
memset(vis,,sizeof(vis));
queue<int> Q;
for(int i=;i<=N;++i){
if(a[i]==val){
vis[i]=true;
Q.push(i);
}
}
while(!Q.empty()){
int x =Q.front();Q.pop();
for(int i=;i<G[x].size();++i){
int v = G[x][i];
if(!vis[v]){
vis[v] = true;
d[v][val] = d[x][val]+;
Q.push(v);
}
}
}
}int main()
{
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
freopen("out.txt","w",stdout);
#endif
int N,M,K,S,u,v;
while(scanf("%d%d%d%d",&N,&M,&K,&S)==){
init(N);
memset(d,,sizeof(d));
for(int i=;i<=N;++i) scanf("%d",&a[i]);
for(int i=;i<=M;++i){
scanf("%d%d",&u,&v);
AddEdge(u,v);
AddEdge(v,u);
}
for(int i=;i<=K;++i){
memset(vis,,sizeof(vis));
BFS(i,N);
}
for(int i=;i<=N;++i){
sort(d[i]+,d[i]+K+);
res[i]=;
for(int j =;j<=S;++j){
res[i]+=d[i][j];
}
} for(int i=;i<N;++i) printf("%d ",res[i]);
printf("%d\n",res[N]);
}
return ;
}