题意分析
考虑最终的生成树，一定包含了权值最小边。设该边为 $(u,v)$，若生成树中不包含 $u,v$，则一定有两条边分别到达 $u,v$。显然这两条边有一条换为 $(u,v)$ 更优。
那么生成树一定形如从 $t$ 到达最小边，之后便是从最小边出来的一些子树（实际上也可以是链，都是等价的）。
为了到达最小边，成为一条链是最优的，否则会有不必要的花费。
确定最小边的一个端点 $x$，求出 $x\sim t$ 的最小权值和最小的链的权值和 $\textit{sum}$ 和链长 $k$ 即可。答案即 $\textit{sum}+(n-k-1)w$。$w$ 为最小边权。
注意到 $x\sim t$ 链上边权除开最后一条边，是单调不降的，否则可以将其放到 $x$ 之后的树上更优。
因此链上每一条边的贡献都是自己的 $1$ 倍，跑最短路即可。
考虑链上两点 $i,s$，若以 $j$ 为中转站更优，的答案为 $2w_{i,j}$。
将所有边权均减去 $w$，在新图上跑 $x\sim t$ 的最短路，答案加上 $(n-1)w$ 即可得到。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=2000,W=1e9;
constexpr const ll inf=0x3f3f3f3f3f3f3f3f;
int n,w[N+1][N+1];
ll dis[N+1];
void Dijkstra(int s){
static bool vis[N+1];
memset(dis,0x3f,sizeof(dis));
memset(vis,0,sizeof(vis));
vis[s]=true;
for(int i=1;i<=n;i++){
dis[i]=w[s][i];
for(int j=1;j<=n;j++){
if(i==j){
continue;
}
dis[i]=min(dis[i],2ll*w[i][j]);
}
}
for(int i=1;i<n;i++){
ll Min=inf;
int x=-1;
for(int j=1;j<=n;j++){
if(vis[j]){
continue;
}
if(dis[j]<Min){
Min=dis[j];
x=j;
}
}
vis[x]=true;
for(int j=1;j<=n;j++){
if(vis[j]){
continue;
}
dis[j]=min(dis[j],dis[x]+w[x][j]);
}
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n;
for(int i=1;i<n;i++){
for(int j=1;j<=n-i;j++){
cin>>w[i][i+j];
w[i+j][i]=w[i][i+j];
}
}
ll Min=inf,s=-1;
for(int i=1;i<=n;i++){
for(int j=i+1;j<=n;j++){
if(w[i][j]<Min){
Min=w[i][j];
s=i;
}
}
}
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
if(i==j){
continue;
}
w[i][j]-=Min;
}
}
Dijkstra(s);
for(int i=1;i<=n;i++){
cout<<dis[i]+(n-1ll)*Min<<'\n';
}
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
