题意

给出n个点完全图，边有边权。枚举x=1~n，找出一棵以x为根的生成树，定义每个点到根的距离di为到根路径上最小的边权，生成树的花费为$∑di$。对于每个x，找出最小花费。
n<=2000

前言

早上男神出的比赛的。。
当时没有做出来。。
但是感觉连$n^3$的分都没拿到真是耻辱啊TAT

反思放前面

①还是要相信自己的想法吧，要不断地把自己的想法挖深
②一定要看准部分分，虽然一直想不到$n^2$的做法，但是$n^3$也是一定要尝试去想的，适当地降低标准往往可以拿到更高的分数
③如果看见，每多选一个就会损失一些代价，那么往往可以直接在原来的代价上减去这个代价
④比赛一定要大胆猜结论。。

题解

下面分为两种做法，第一个是我一开始的方向，第二个是男神的方向

下文记所有边权的最小值是mn，所连出去的边权包含mn的叫做关键点

n^3的做法 ①

容易想到，最后答案肯定就是由i连出一堆边，然后连到一个最小值
然后后面就挂一个子树就可以了
那怎么知道连出一堆边是什么呢？
我们假设，对于每一个点，他的代价都是mn
那么对于没有取到mn的点，假设他的值是x
那么他的代价就会变大$x-mn$
我们可以对于所有边权减去mn
我们可以对于每个点跑一个最短路，终点是任意一个关键点
由于这是一个完全图，最短路是$n^2$的
于是总体做法就是$n^2$的
至于路径最小值
我们可以在DIJ的时候记录一下这个最短路的边权最小值，每一次比较一下就可以取小的了，其实不需要每一次取小，只需要在下一个是关键点的时候再比较就可以了，但是这样方便，在下文$n^2$的做法可以证明这个做法的

我比较懒，因为这个代码不在这台电脑上，所以就不给了。。

n^2的做法①

考虑上面的做法，每一次都跑一次实在是太慢了
仔细观察的话，我们可以发现一个性质，那就是肯定存在一种方案，使得一开始选的边都是递减的，最后一个可能递增的就是下一个连接的点就是关键点
这个正确性还是很好证的啊，自己动动脑就好了
我们依然让边权减去mn
那么我们考虑一下，那么我们对于一个点i
我们一直走递减的边，走到j
我们可以知道，肯定有一条最短路$dis[i][j]$是可以满足这个条件的
然后，我们有两种操作，就是这个点就是关键点了，那么答案就是dis[i][j]，因为减去之后，这条边权已经是0了，所以加上最小边权g[i]，没有影响，为了方便，我们加上$dis[i][j]+g[j]*2$，为什么？下面就知道了
第二个操作，就是再走两条边走到关键点？那一条边的情况呢？因为如果下一条边是递减的，那么会在第一个情况枚举到。如果不是，那么边权就是要上一条边枚举到，就是这个了。容易知道，这个的答案就是$dis[i][j]+g[j]*2$
但是这样还是$n^3$的，怎么优化？
这时候，我们可以从j开始，倒着往前跑，用dij来优化
那么就可以做到$n^2$了

n^3的做法② la1la1la

还是先把所有边权减去mn
现在问题变成对每个点x，找出到标记的点的最短路，并且可以用先走的边权代替后走的边权。 不妨从标记点开始找，让后走的边权代替先走的边权。
一个朴素的想法是f[i][j]表示走到点i，有j条边要使用后面的边权的最短路。f[i][j]可以转移到f[k][0]或f[k][j+1]
容易知道这个DP的正确性
首先，他的答案肯定不会变小，其次，他肯定可以搜出正确答案
虽然过程的答案不一定是合法的，但是肯定可以搜出最后的答案
然而这个做法是$n^3$的

n^3的做法② la1la1la

但是考虑做最短路的目的是找到一个标记点，走到很多个中间点显然不是什么好方案。具体来说，从i走j条边到k，只是为了使用最后一条边权(s,k)，那为什么不直接i->s->k呢？所以f[i][j]中的j只需要取0,1。
于是就可以了

解法①的代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const LL MAX=(1<<30);
const LL N=2005;
LL n;
LL a[N][N];
LL f[N];
bool vis[N];
int main()
{memset(vis,false,sizeof(vis));memset(f,127,sizeof(f));LL mn=MAX;scanf("%I64d",&n);for (LL u=1;u<=n;u++)for (LL i=u+1;i<=n;i++){scanf("%I64d",&a[u][i]);a[i][u]=a[u][i];mn=min(mn,a[u][i]);}for (LL u=1;u<=n;u++)for (LL i=1;i<=n;i++)if (u!=i){a[u][i]-=mn;f[u]=min(f[u],2*a[u][i]);}for (LL u=1;u<=n;u++){LL t=0;for (LL i=1;i<=n;i++)if (f[t]>f[i]&&vis[i]==false)t=i;vis[t]=true;for (LL i=1;i<=n;i++)   f[i]=min(f[i],f[t]+a[t][i]);}for (LL u=1;u<=n;u++) printf("%I64d\n",f[u]+(n-1)*mn);return 0;
}

解法②的代码

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<cstring>
#include<queue>
using namespace std;
typedef long long LL;
const LL MAX=1e15;
const LL N=2005;
LL n;
LL a[N][N];
bool vis[N];
LL f[N][2];
bool b[N][2];
queue<pair<int,int> > q;
bool o[N];
void SPFA ()
{memset(b,false,sizeof(b));memset(f,127,sizeof(f));for (LL u=1;u<=n;u++){if (o[u]==false) continue;f[u][0]=0;b[u][0]=1;q.push(make_pair(u,0));}while (!q.empty()){LL i=q.front().first,j=q.front().second;for (LL u=1;u<=n;u++){if (u==i) continue;LL t=min(f[i][j]+(j+1)*a[i][u],MAX);if (t<f[u][0]){f[u][0]=t;if (b[u][0]==false){b[u][0]=true;q.push(make_pair(u,0));}}t=f[i][j];if (j==0&&t<f[u][1]){f[u][1]=t;if (b[u][1]==false){b[u][1]=true;q.push(make_pair(u,1));}}}q.pop();b[i][j]=false;}
}
int main()
{memset(o,false,sizeof(o));memset(vis,false,sizeof(vis));memset(a,127,sizeof(a));LL mn=MAX;scanf("%I64d",&n);for (LL u=1;u<=n;u++)for (LL i=u+1;i<=n;i++){scanf("%I64d",&a[u][i]);a[i][u]=a[u][i];mn=min(mn,a[u][i]);}for (LL u=1;u<=n;u++)for (LL i=1;i<=n;i++)if (u!=i){a[u][i]-=mn;if (a[u][i]==0) o[u]=o[i]=true;}SPFA();for (LL u=1;u<=n;u++) printf("%I64d\n",f[u][0]+(n-1)*mn);return 0;
}