题目分析：
首先我们观察一下，肯定得先正着跑一遍最短路再建反图跑一遍最短路,这样可以对于所有的 (i) 求出 (dis(b + 1, i)) 以及 (dis(i, b + 1)) 。
然后我们继续观察，题目里面有一个条件是： 同一个子集内的点两两之间会互相发送信息。
于是我们可以知道
性质一：
- 每一个点的贡献实际上只跟自己所处在的子集的大小有关，跟哪一些元素在一起其实并不重要。假设点 (i) 所处的集合大小为 (siz) ,那么它对于答案的贡献就会是 ((dis(i, b + 1) + dis(b + 1, i)) * (siz - 1))。
下面我们把 ((dis(i, b + 1) + dis(b + 1, i))) 叫做 (w_i)
性质二:
- 根据性质一，我们可以知道，对于 (w_i) 相近的一些数我们总是将它们分到一组更优。为什么呢？感性的用贪心来思考这个问题，因为如果它们的 (w_i) 比较小，我们总是希望它们能够与相对较多 的元素在同一个集合，毫无疑问的，相近的一些搭配在一起更好，如果 (w_i) 比较大也是类似的。
通过性质二的分析，我们将 ([1,b]) 所有的点按照 (w_i) 排序。问题就转化为了将一个长度为 (b) 的 单调不减序列 划分成 (s) 段，每一段的花费为这一段的数的和 * (这一段的长度 (-) (1))。
这样的话我们就轻松写出一个 (n^3) 的 (dp):
设 (dp[i][j]) 表示将前 (i) 个数分成 (j) 段的最小费用。
那么 (dp[i][j] = Min(dp[k][j - 1] + (sum[i] - sum[k]) * (i - k - 1)); (0 <= k < i))
这样的话是肯定过不了的。
考虑优化：
首先上面 (dp[i][j]) 可以通过滚动数组优化为一维，这样子空间复杂度就变成了 O((n))。
在做划分第 (j) 段的时候，打表知道 随着 (i) 往右边移动，对应的最优决策点是不断右移的。
证明：
首先明确一点，我们进行划分的序列是 单调不减 的。下面称这个序列为 (A) 序列，这个序列的第 (i) 项我们就称之为 (A_i)。
我们假设现在在对 (dp[i]) 进行决策，(dp[i - 1]) 的最佳决策点是 (k (0 <= k < i))。
那么倘若 (dp[i]) 的最优决策点为 (j) 并且 (j < k)。
那么意味着 :
(dp[k] + (sum[i] - sum[k]) * (i - k - 1) > dp[j] + (sum[i] - sum[j]) * (i - j - 1))
但是又同时有：
(dp[k] + (sum[i - 1] - sum[k]) * (i - k - 2) < dp[j] + (sum[i - 1] - sum[j]) * (i - j - 2))
上下两式作差则有(中间的化简过程就略了，读者可以自行化简，其中重要的一步就是要将 (sum[i]) 转化为 (sum[i - 1] + A[i]))：
((i - k - 2)A_i + sum[i] - sum[k] > (i - j - 2)A_i + sum[i] - sum[j])
这个式子显然就矛盾了。所以可以知道，无论如何最佳决策点都是 单调不减 的。
于是时间复杂度： O((n^2)) , 空间复杂度: O((n)) 就水过去了。
Code
#include <bits/stdc++.h>
using namespace std;
#define int long long
inline int read() {
int x = 0 , flag = 1;
char ch = getchar();
for( ; ch > '9' || ch < '0' ; ch = getchar()) if(ch == '-') flag = -1;
for( ; ch >= '0' && ch <= '9' ; ch = getchar()) x = (x << 3) + (x << 1) + ch - '0';
return x * flag;
}
const int MAXN = 5e4 + 50;
int n,r,b,s;
int disA[MAXN], disB[MAXN],start[MAXN],tot = 0,book[MAXN];
int sum[MAXN], dp[MAXN][2];
struct Edge {
int next, to, w;
} edge[MAXN << 1];
struct Dijk {
int id, dis;
bool operator <(const Dijk& A) const {return A.dis < dis;}
} ;
struct Point {
int val,id;
} P[MAXN];
priority_queue <Dijk> q;
void add(int from, int to, int w) {
edge[++tot].next = start[from];
edge[tot].to = to;
edge[tot].w = w;
start[from] = tot;
return ;
}
void Dijkstra(int *dis,int op) {
memset(book,0,sizeof(book));
for(int i = 1 ; i <= n ; i ++) dis[i] = 1e9 + 7;
dis[b + 1] = 0;
q.push({b + 1, 0});
while(!q.empty()) {
int x = q.top().id, d = q.top().dis; q.pop();
if(dis[x] != d) continue;
book[x] = 1;
for(int i = start[x] ; i ; i = edge[i].next) {
int to = edge[i].to, w = edge[i].w;
if(i % 2 == op) continue;
if(dis[x] + w < dis[to]) {
dis[to] = dis[x] + w;
if(!book[to]) q.push({to, dis[to]});
}
}
}
return ;
}
bool cmp(Point a, Point b) {return a.val < b.val;}
int Q[5005];
signed main() {
n = read(), b = read(), s = read(), r = read();
for(int i = 1 ; i <= r ; i ++) {
int u = read(), v = read(), w = read();
add(u, v, w); add(v, u, w);
}
Dijkstra(disA, 0); Dijkstra(disB, 1);
for(int i = 1 ; i <= n ; i ++) {
P[i].val = disA[i] + disB[i];
P[i].id = i;
}
sort(P + 1, P + 1 + b , cmp);
for(int i = 1 ; i <= b ; i ++) sum[i] = sum[i - 1] + P[i].val;
int now = 1;
for(int i = 1 ; i <= b ; i ++) dp[i][1] = sum[i] * (i - 1);
for(int j = 2 ; j <= s ; j ++) {
now ^= 1;
memset(Q, 0, sizeof(Q));
for(int i = 1 ; i <= b ; i ++) dp[i][now] = 1e18 + 7;
for(int i = j ; i <= b ; i ++) {
for(int k = i - 1 ; k >= Q[i - 1] ; k --) {
if(dp[k][now ^ 1] + (sum[i] - sum[k]) * (i - k - 1) < dp[i][now]) Q[i] = k;
dp[i][now] = min(dp[i][now], dp[k][now ^ 1] + (sum[i] - sum[k]) * (i - k - 1));
}
}
}
cout << dp[b][now];
return 0;
}