Acwing第35场周赛T3三元组----多种解法

难得AK一次，看看大佬T3题解，发现可以有多种解法

#include 
#include 
#include 

using namespace std;
const int N = 3010,INF = 0x3f3f3f3f;
int a[N],b[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i=0;ia[i])d=min(d,b[j]);
        if(c!=INF&&d!=INF)res=min(res,b[i]+c+d);
    }
    if(res==0x3f3f3f3f)cout<<-1< 
解法二：预处理 
多开一个数组用来存对于每个中间的数，满足条件的他的前边数的最小值
 然后再去枚举第三个数
 
#include 
#include 
#include 

using namespace std;
const int N = 3010;
int a[N],b[N],c[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i=0;ia[j]&&c[i]>b[j])c[i]=b[j];
    
    for(int i=0;ia[i])res=min(res,c[i]+b[i]+b[j]);
    if(res==0x3f3f3f3f)cout<<-1< 
解法三：简单DP写法 
#include 
#include 
#include 

using namespace std;
const int N = 3010;
int f[3][N];
int a[N],b[N];
int n;
int main()
{
    scanf("%d", &n);
    for(int i=0;ia[j])
            {
                f[1][i]=min(f[1][i],f[0][j]+b[i]);
                f[2][i]=min(f[2][i],f[1][j]+b[i]);
            }
            res=min(res,f[2][i]);
        }
    }
    if(res==0x3f3f3f3f)cout<<-1<