题目
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;
}