题目链接
Codeforces 986A Fair
Task 1
由于城市个数巨大（\(10^5\)），我们考虑存储每个点到各商品产地最短距离，即 dis 数组。只需对于每个点跑一遍单源最短路，再更新答案即可，时间复杂度 \(O(n^2)\)。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N=1e5+10,K=105;
int n,m,k,s;
int a[N],dis[N][K],tmp[N];
vector<int> f[N];void bfs(int x){memset(tmp,0x3f,sizeof tmp);queue<int> q;q.push(x),tmp[x]=0;while (!q.empty()){int u=q.front();q.pop();for (auto v:f[u]){if (tmp[u]+1<tmp[v]) q.push(v),tmp[v]=tmp[u]+1;}}for (int i=1;i<=n;++i) dis[i][a[x]]=min(dis[i][a[x]],tmp[i]);
}
int main(){scanf("%d%d%d%d",&n,&m,&k,&s);for (int i=1;i<=n;++i) scanf("%d",a+i);while (m--){int u,v;scanf("%d%d",&u,&v);f[u].push_back(v);f[v].push_back(u);}memset(dis,0x3f,sizeof dis);for (int i=1;i<=n;++i) bfs(i);for (int i=1;i<=n;++i){sort(&dis[i][1],&dis[i][k+1]);ll ans=0;for (int j=1;j<=s;++j) ans+=dis[i][j];printf("%lld ",ans);}return 0;
}
Task 2
注意到我们并不在乎具体是哪个城市提供了什么商品，只需要知道某一城市拿到商品运费最小为几。所以，我们可以对每种商品考虑。每次 bfs，将这个商品所有产地入队，求出这个商品产地到每个城市的最小运费。这样就只需做 \(k\) 次 bfs，时间复杂度 \(O(nk\log{k})\)，瓶颈在排序。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;const int N=1e5+10,K=105;
int n,m,k,s;
int a[N],dis[N][K];
vector<int> f[N],g[K];void bfs(int x){queue<int> q;for (auto i:g[x]) q.push(i),dis[i][x]=0;while (!q.empty()){int u=q.front();q.pop();for (auto v:f[u]){if (dis[u][x]+1<dis[v][x]) q.push(v),dis[v][x]=dis[u][x]+1;}}
}
int main(){scanf("%d%d%d%d",&n,&m,&k,&s);for (int i=1;i<=n;++i) scanf("%d",a+i),g[a[i]].push_back(i);while (m--){int u,v;scanf("%d%d",&u,&v);f[u].push_back(v);f[v].push_back(u);}memset(dis,0x3f,sizeof dis);for (int i=1;i<=k;++i) bfs(i);for (int i=1;i<=n;++i){sort(&dis[i][1],&dis[i][k+1]);ll ans=0;for (int j=1;j<=s;++j) ans+=dis[i][j];printf("%lld ",ans);}return 0;
}