CLICK HERE
一共有n个城市分别生产k种商品，现在需要知道从每个城市出发至少得到s种不同的商品的最短距离。
第一次看还以为是最短生成树，但这样子可以求获得所有商品的最短距离而无法求得s种的。所以换一种思路，使用搜索求出第i个城市出发到第j个商品的最短距离。但这样子至少要n次搜索，n的数据最大为1e5明显会超时。 于是用一种巧妙的方法，看到种类的数目最大为100，不妨以种类为循环次数进行bfs，这样子就可以做出来了。
#include <cstdio> #include <cstring> #include <ctype.h> #include <cstdlib> #include <cmath> #include <climits> #include <ctime> #include <iostream> #include <algorithm> #include <deque> #include <vector> #include <queue> #include <string> #include <map> #include <stack> #include <set> #include <list> #include <numeric> #include <sstream> #include <iomanip> #include <limits> #define MST(a, b) memset(a, b, sizeof(a)) using namespace std; typedef long long ll; typedef pair<int, int> P; const int INF = 0xfffffff; const int MAXM = 150 + 50; const int MAXN = 1e5 + 100; int dis[MAXN][MAXM]; bool vis[MAXN]; vector <int> group[MAXM], g[MAXN]; int n, m, k, s, tmp; void init() { for (int i = 1; i <= k; i++) group[i].clear(); for (int i = 1; i <= n; i++) g[i].clear(); MST(dis, INF); } void bfs(int type) { MST(vis, false); queue <P> q; for (int i = 0; i < group[type].size(); i++) { q.push(make_pair(group[type][i], 0)); vis[group[type][i]] = true; } while (!q.empty()) { P p = q.front(); q.pop(); dis[p.first][type] = p.second; for (int i = 0; i < g[p.first].size(); i++) { int v = g[p.first][i]; if (vis[v]) continue; vis[v] = true; q.push(make_pair(g[p.first][i], p.second + 1)); } } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin >> n >> m >> k >> s; init(); for (int i = 1; i <= n; i++) { cin >> tmp; group[tmp].push_back(i); } while (m--) { int u, v; cin >> u >> v; g[u].push_back(v); g[v].push_back(u); } for (int i = 1; i <= k; i++) bfs(i); for (int i = 1; i <= n; i++) { int sum = 0; sort(dis[i] + 1, dis[i] + 1 + k); for (int j = 1; j <= s; j++) sum += dis[i][j]; cout << sum; if (i == n) cout << endl; else cout << " "; } }