本题为BFS的思维题
1)如果bfs所有点O(N^2)超时
2)发现商品类型只有k(<= 100), 则可以找到每一种商品到不同的点的最短距离
3)排序找到每个点位路前s个短路对应的商品
#include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
#include <queue>
using namespace std;
const int N = 1e5 + 10, M = N * 2;
int n, m, k, s;
int w[N], d[N][102];
int h[N], e[M], ne[M], idx;
void add(int a, int b)
{
e[idx] = b; ne[idx] = h[a]; h[a] = idx ++ ;
}
void bfs(int x)
{
queue<int> q;
for (int i = 1; i <= n; i ++ )
if (w[i] == x) q.push(i), d[i][x] = 1;
while (q.size())
{
int t = q.front(); q.pop();
for (int i = h[t]; i != -1; i = ne[i])
{
int j = e[i];
if (d[j][x]) continue;
d[j][x] = d[t][x] + 1;
q.push(j);
}
}
}
int main()
{
scanf("%d%d%d%d", &n ,&m, &k, &s);
for (int i = 1; i <= n; i ++ )
scanf("%d", &w[i]);
memset(h, -1, sizeof h);
while (m -- )
{
int a, b;
scanf("%d%d", &a, &b);
add(a, b); add(b, a);
}
for (int i = 1; i <= k; i ++ ) bfs(i);//找到各类商品到个点位的最短路
for (int i = 1; i <= n; i ++ )
{
int res = 0;
sort(d[i] + 1, d[i] + k + 1);//对于一个点位排序不同商品到该点位的最短路
for (int j = 1; j <= s; j ++)//找到前s个短路
res += d[i][j] - 1;
printf("%d ", res);
}
puts("");
return 0;
}
太棒啦 大爱链式前向星