题目

http://bailian.openjudge.cn/practice/2355/

思路

我觉得可以用 狄杰斯特拉但是我写完 wa 了不知道为啥
dp[i]表示到i的最短路径，直接 dp 求解，i 从 1到n遍历求解dp[i],只会用到 dp[k] k < i

源码

//
//  2355.cpp
//  test
//
//  Created by bytedance on 2020/9/7.
//  Copyright © 2020 bytedance. All rights reserved.
//

#include <iostream>
#include <vector>
#define INF 999999999999
using namespace std;

long c1,c2,c3,l1,l2,l3;
int n,s,e;
long pre[10005]={0};
int main(){
    cin >>l1>>l2>>l3;
    cin >> c1>>c2>>c3;
    cin >> n;
    cin >>s>>e;
    if(s>e)swap(s,e);
    for(int i = 2;i <= n;++i){
        cin >> pre[i];
    }
    vector<long>d(n+1,INF);
    d[s] = 0;
    for(int i = s+1;i <= n;++i){
        for(int j = i-1;j>=s;--j){
            long dis = pre[i]-pre[j];
            if(dis<=l1)d[i]=min(d[i],d[j]+c1);
            else if(dis<=l2)d[i] = min(d[i],d[j]+c2);
            else if(dis<=l3)d[i] = min(d[i],d[j]+c3);
            else break;
        }
    }
    cout<<d[e];
    return 0;
}