1211: 小镇购物
题目描述
CSU镇上有n个商店，n个商店有m条双向小路相连，在这n个商店里共有k种不同商品，每个商店只有一种商品，每条路的权重都为1。现问你从每个商店出发，买够k种商品中的s种商品所需的最小代价,每个商店可以同时派出多个人买不同商品，每人仅能购买一件，买够即可。
输入
输入包含多组测试用例。
对于每一组输入包含四个数字n ,m, k,s (1<=n<=m<=1e5 , 1<=s<=k<=min(n,100))
分别代表商店数，小路数，商品种数，需要的商品数。
接下来n个数 a1,a2…an (1<=ai<=k),ai代表第i个商店的商品编号。
接下来m行小路(u,v),u≠v,代表商店u和v之间有小路连接。
输出
输出n个数字，第i个数字代表从商店i出发买够s种商品所需的最小代价。
样例输入
5 5 4 3
1 2 4 3 2
1 2
2 3
3 4
4 1
4 5
7 6 3 2
1 2 3 3 2 2 1
1 2
2 3
3 4
2 5
5 6
6 7
样例输出
2 2 2 2 3
1 1 1 2 2 1 1
思路
可以同时派出多个人且不计算回程所耗的代价，因此只要求出每个商店取得其它商品的最短距离即可。若使用最短路径算法则其时间复杂度为 o（n^3），肯定会超时。观察可以得到，商品最多为 100 种，商店到商品的距离即商品到商店的距离，故可以枚举这 k 种商品，对 k 种商品分别使用广度优先搜索，计算出每个商店 i 得到第 j 种商品的最短距离 ans[i] [j]。最后对于每个商店求出路径最小的前 s 种商品的路径和即可，可以使用 nth_element()。
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int a[N];// a[i]--商店 i 的商品 j, ans[i][j]--商店 i 到商品 j 的最短距离
int main()
{
// freopen("in.cpp", "r", stdin);int n, m, k, s, u, v;while(scanf("%d%d%d%d", &n, &m, &k, &s) != EOF){
vector<vector<int>> ans(n + 1, vector<int>(k + 1, 0x3f)); // 一开始直接写的 int ans[N][105], 使用 memset，一直超时。坑了我一天。for(int i = 1; i <= n; i++)scanf("%d", &a[i]);
// vector<int> map[N];vector<vector<int>> map(n+1);for(int i = 1; i <= m; i++){
scanf("%d%d", &u, &v);map[u].push_back(v);map[v].push_back(u);}// 枚举每种商品 for(int i = 1; i <= k; i++){
vector<bool> vis(n + 1, false);queue<int> q;for(int j = 1; j <= n; j++){
if(a[j] == i){
q.push(j);vis[j] = true;ans[j][i] = 0;}}while(!q.empty()){
u = q.front();q.pop();for(int j = 0; j < (int)map[u].size(); j++){
v = map[u][j];if(!vis[v]){
ans[v][i] = ans[u][i] + 1;q.push(v);vis[v] = true; }}}}for(int i = 1; i <= n; i++){
nth_element(ans[i].begin() + 1, ans[i].begin() + s, ans[i].end());int r = 0;for(int j = 1; j <= s; j++)r += ans[i][j];printf("%d ", r);}printf("\n");}return 0;
}