题目描述

Lyk去推塔。但是推第n座塔必须先推了第1~n-1座塔。

为了加快速度lyk召唤出了szh和txm。求lyk和他的召唤兽们为了推完所有塔所经过的最短距离。

 

输入

第一行一个数N，代表一共要去多少个城市。

下面N-1 行，对于第 i 行，有 n-i 个数，表示第 i 个城市分别和第i+1, i+2, i+3, ……, N 的距离（距离<=10000）

 

输出

一个数，表示最短距离

 

样例输入

51 1 1 233 33 3333 3333

样例输出

36

提示

 

Constraints

对于30%，n<=10

对于100%，n<=100

第一遍做时爆搜爆0

DP即可

f[i][j][k]表示推到第i座塔，其余两只怪兽在j,k时的最短距离

f[i+1][j][i]=min(f[i+1][j][i],f[i][j][k]+dist[k][i+1]);

f[i+1][j][k]=min(f[i+1][j][k],f[i][j][k]+dist[i][i+1]);

[i+1][i][k]=min(f[i+1][i][k],f[i][j][k]+dist[j][i+1]);

第一遍暴力floyd预处理出所有点对间的最短距离

#include
      
       #include
       
        #include
        
         using namespace std;int a[105][105],dp[105][105][105],n;void floyd(){    for(int i=1;i<=n;i++)        for(int j=i+1;j<=n;j++)               for(int k=j+1;k<=n;k++)                   if(i!=k&&j!=k&&i!=j)                   if(a[i][j]+a[j][k]
        
       
      

题意难懂~~