题目大意：给你n个点的横坐标，及其相应的4个相关值。给定起点和终点，可以任意跳跃，要求每个点只能走一次，并且从起点走到终点。求消耗的最小值。
由两种消耗
|xi - xj| + ci + bj if j < i
|xi - xj| + di + aj otherwise (j > i)
范围：5000个点
题解：由于考虑顺序的话复杂度太大而且无法有效地控制终点位置。所以可以把此题看做一个最短路问题，在S->E的路径上不断加点，每次记下最小消耗的节点，正确性可以由最短路算法推导。
在路径上不断加点，十分经典的处理方法。
#include<bits/stdc++.h> using namespace std; #define maxn 5100 int n,s,e; int x[maxn],a[maxn],b[maxn]; int c[maxn],d[maxn],next[maxn]; long long f(int i,int j) { long long tmp=abs(x[i]-x[j]); if(i<j) tmp+=d[i]+a[j]; else tmp+=c[i]+b[j]; return tmp; } 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]); next[s]=e; long long tmp,ans,cnt; ans=f(s,e); for(int i=1;i<=n;i++) { if(i==s||i==e) continue; cnt=0x7f7f7f7f7f7f7f7fLL; int pos=0; for(int j=s;j!=e;j=next[j]) { tmp=f(j,i)+f(i,next[j])-f(j,next[j]); if(tmp<cnt) { cnt=tmp; pos=j; } } ans+=cnt; next[i]=next[pos]; next[pos]=i; } cout<<ans<<endl; return 0; }