[最短路 杂题] Codeforces 806D VK Cup 2017 Round 3 D. Perishable Roads

VK Cup 2017 Round 3 D. Perishable Roads"/>

[最短路 杂题] Codeforces 806D VK Cup 2017 Round 3 D. Perishable Roads

我们把所有边权都减去最小值 然后发现 肯定是一条链然后下面挂着一条0边 然后挂着一整颗子树 子树中贡献都是0 那么我们要最小化那条链
我们发现这条链上如果有连续的权值为 0⋯a,b,c,d⋯且b>c $0\cdots a,b,c,d\cdots \text 且 b>c$
那么我们把 a,b $a,b$换成一条边答案不会更劣 唯一不行的就是 b <script type="math/tex" id="MathJax-Element-77">b</script>就是链头没有边 之后的边必然是递增的 这样就可以做一个最短路了

#include<cstdio>
#include<cstdlib>
#include<algorithm>
using namespace std;
typedef long long ll;const int N=2005;
#define read(x) scanf("%d",&(x))int n,w[N][N];
ll dis[N];
int vst[N];
int minv;int main(){freopen("t.in","r",stdin);freopen("t.out","w",stdout);read(n); minv=1<<30;for (int i=1;i<=n;i++)for (int j=i+1;j<=n;j++){read(w[i][j]); w[j][i]=w[i][j];minv=min(minv,w[i][j]);}for (int i=1;i<=n;i++){dis[i]=1LL<<60;for (int j=1;j<=n;j++)if (i^j){w[i][j]-=minv;dis[i]=min(dis[i],(ll)w[i][j]<<1);}}for (int i=1;i<=n;i++){int k=0;for (int j=1;j<=n;j++)if (!vst[j] && (!k || dis[j]<dis[k]))k=j;vst[k]=1;for (int j=1;j<=n;j++)dis[j]=min(dis[j],dis[k]+w[k][j]);}for (int i=1;i<=n;i++)printf("%I64d\n",dis[i]+(ll)(n-1)*minv);return 0;
}