题意
给 \(n\) 个点，已知坐标 \(x_i\)，参数 \(a_i,b_i,c_i,d_i\)。可以根据坐标和参数计算从一个点跳到另一个点的花费。
要求从 \(s\) 点到 \(t\) 点且经过所有仅一次的最小总花费。
思路
第一次接触这样贪心的题，感觉很巧妙
做一个链表，最开始为 \(s\)->\(e\)。
然后从 \(1\) 到 \(n\) 依次插入链表，(\(s\) 与 \(e\) 除外)
至于插到哪个位置，因为 \(k\) 插到 \(i\)->\(j\) 中，花费增加为 \(len[i][k]+len[k][j]-len[i][j]\)，
那么找这个最小的增加花费的位置就是要插入的位置了
代码
不想写链表，于是直接写了个vector，
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const int inf=0x3f3f3f3f;
const LL INF=0x3f3f3f3f3f3f3f3f;
int n,s,e,x[5010],a[5010],b[5010],c[5010],d[5010];
LL len[5010][5010],ans;
vector<int> vec;
int main(){
scanf("%d%d%d",&n,&s,&e);
for(int i=1;i<=n;i++) scanf("%d",&x[i]);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++) scanf("%d",&c[i]);
for(int i=1;i<=n;i++) scanf("%d",&d[i]);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
if(i==j) continue;
if(j<i) len[i][j]=(LL)abs(x[i]-x[j])+c[i]+b[j];
else len[i][j]=(LL)abs(x[i]-x[j])+d[i]+a[j];
}
vec.push_back(s);
vec.push_back(e);
ans=len[s][e];
for(int i=1;i<=n;i++){
if(i==s||i==e) continue;
int pos=1;
LL temp=ans-len[vec[0]][vec[1]]+len[vec[0]][i]+len[i][vec[1]];
for(int j=2;j<vec.size();j++){
LL tp=ans-len[vec[j-1]][vec[j]]+len[vec[j-1]][i]+len[i][vec[j]];
if(tp<temp) pos=j,temp=tp;
}
ans=ans-len[vec[pos-1]][vec[pos]]+len[vec[pos-1]][i]+len[i][vec[pos]];
vec.insert(vec.begin()+pos,i);
}
cout<<ans<<endl;
return 0;
}