题目描述：
有一个 \(n\) 个点的图，对于每两个点 \((i,j)\) 之间都有一条长度为 \(w_{i,j}\) 的无向边。
给你一个点 \(t\)，你需要构造一棵以 \(t\) 为根的生成树，使得\(\sum\limits_{i=1}^{n}s(i,t)\) 尽量小。\(s(i,t)\) 为 \(i\rightarrow t\) 的树上路径上的最小权值。
你需要对于每个 \(t\) 都求出答案。
数据范围：
\(n\le 2000\)
\(1\le w_i\le 10^9\)
思路：
首先我们手摸一下样例，显然我们希望尽可能使得整体的距离最小，则需要满足尽可能多的点都是经过最短边然后到达 \(t\)。
在进行正式的讲解之前，我们先进行一些定义：
- \(mn\) 表示最小的边长，\(st\) 表示最小的边连接的点
所以我们就可以将整个图分为两个部分：
- \(st\Rightarrow t\) 的这条链
- 以 \(st\) 为根且到 \(t\) 最小值为 \(mn\) 的一棵树
注意：最小边在树和链的连接处
然后我们分别考虑怎么计算这个两个部分。
对于链的部分，我们不难发现一个性质：必定存在一种最优方案，使得从st到t的这条链上边权单调不降
这个性质的证明也是比较简单的。
我们考虑反证法：如果有一条递减的边，则把这个点放到链起点的位置显然不会更劣。所以问题就转换为求一条最短路径的长度
所以我们以 \(st\) 为起点跑一边最短路，就可以得到以 \(i\) 为终点的链上的最小代价。
然后我们考虑如何计算树的部分的答案：
令整条路径上经过的点的数量为 \(x\)，则一共 \(n-x\) 个在树上的点（这里的树不是整棵生成树）然后贡献就是 \((n-x)\times mn\)
然后我们发现这个东西不是很好计算，所以我们不妨对原式进行一些修改（这个改动我根本没想到）
将 \(x\) 的定义变为链上的边的数量，则贡献变为 \((n-x-1)\times mn\to (n-1)\times mn-x\times mn\)
所以我们不妨对于原图中的每一条边都减去 \(mn\)。
这样最后的答案就可以转变为 \(dis_t+(n-1)\times mn\)
后记：
关于一些疑问：
1. 为什么只需要进行一个 \(mn\) 两端的点就可以了？
仔细观察代码，我们在代码中有这样的几行
for(int j=1;j<=n;j++)if(j!=i)dis[i]=min(dis[i],g[j][i]*2);
所以我们不难发现，这个东西实际上包含了另外一种情况，具体的可以画图理解一些：
.png)
对于这个图，显然 \(st=1\)
这个涉及到在处理的时候与 \(st\) 连边的有哪些点？
- 直接连边
- 经过一个转折点
点击查看代码
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=2005;
const int inf=1e18;
int n;
int g[maxn][maxn];
int mn=inf,st;
int vis[maxn],dis[maxn];
void Dijkstra(int st){
for(int i=1;i<=n;i++)dis[i]=inf,vis[i]=0;
vis[st]=1;
for(int i=1;i<=n;i++){
dis[i]=g[st][i];
for(int j=1;j<=n;j++)if(j!=i)dis[i]=min(dis[i],g[j][i]*2);
}
for(int i=1;i<n;i++){
int u=-1;
for(int j=1;j<=n;j++){
if(!vis[j]&&(u==-1||dis[j]<dis[u]))u=j;
}
vis[u]=1;
for(int v=1;v<=n;v++){
dis[v]=min(dis[v],dis[u]+g[u][v]);
}
}
}
signed main(){
scanf("%lld",&n);
for(int i=1;i<n;i++){
for(int j=i+1;j<=n;j++){
scanf("%lld",&g[i][j]);
g[j][i]=g[i][j];
if(mn>g[i][j]){
mn=g[i][j];
st=i;
}
}
}
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
g[i][j]-=mn;
g[j][i]-=mn;
}
}
Dijkstra(st);
for(int i=1;i<=n;i++){
printf("%lld\n",dis[i]+mn*(n-1));
}
return 0;
}
可能讲的有些凌乱，还请多多海涵