题目链接

Codeforces Round 977 (Div. 2）E1 Digital Village (Easy Version)

思路

首先，我们注意到$n$的最大值只有$400$。

因此，我们可以先用$Floyd$算法预处理出任意两座城市之间的最大延迟时间。

之后，我们通过在线操作，每次贪心地选出最优的一个城市，并不断更新答案。

即，我们先选出$k=1$时的最优解，之后从剩下的点里面挑出一个能够使$k=2$时最优的点，以此类推。

代码

#include <bits/stdc++.h>
using namespace std;
#define int long long
const int N = 4e2 + 5;
const int mod = 998244353;
const int inf = 0x3f3f3f3f3f3f3f3f;
int n, m, p;
void solve()
{cin >> n >> m >> p;vector<int>city(p);for (int &val : city){cin >> val;}vector<vector<int>>dist(n + 1, vector<int>(n + 1, inf));for (int i = 1, u, v, w; i <= m; i++){cin >> u >> v >> w;dist[u][v] = min(dist[u][v], w);dist[v][u] = min(dist[v][u], w);}for (int i = 1; i <= n; i++)dist[i][i] = 0;for (int k = 1; k <= n; k++){for (int i = 1; i <= n; i++){for (int j = 1; j <= n; j++){dist[i][j] = min(dist[i][j], max(dist[i][k], dist[k][j]));}}}vector<int>ans(n + 1);int sum = inf, idx = -1;for (auto u : city){int res = 0;for (auto v : city){res += dist[u][v];}if (sum >= res){idx = u;sum = res;for (auto v : city){ans[v] = dist[u][v];}}}set<int>st;st.insert(idx);cout << sum << " ";for (int i = 2; i <= n; i++){if (sum == 0){cout << sum << " ";continue;}int maxx = 0;idx = -1;for (auto u : city){if (st.count(u)) continue;int res = 0;for (auto v : city){if (st.count(v)) continue;if (ans[v] > dist[u][v]){res += ans[v] - dist[u][v];}}if (maxx <= res){maxx = res;idx = u;}};st.insert(idx);sum -= maxx;for (auto v : city){if (st.count(v)) continue;ans[v] = min(ans[v], dist[idx][v]);}cout << sum << " ";}cout << endl;
}
signed main()
{ios::sync_with_stdio(false);cin.tie(0), cout.tie(0);int test = 1;cin >> test;for (int i = 1; i <= test; i++){solve();}return 0;
}