この問題は、 巡回セールスマン型の bitDP を用いて解くことができます。

\(dp[\) 既に訪れた都市の集合 \(S\) \(][\) 現在いる都市 \(k\) \(]=\{\) その状態に至るまでの最小コスト \(\}\)

始点が固定なので、初期化に工夫をすることで持つべき DP テーブルの大きさを半分程度に抑えることができます。

時間計算量は \(O(2^NN^2)\) 、空間計算量は \(O(2^NN)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;

using ll=long long;

int main(){
  int N;
  cin >> N;
  N--;
  ll Vs;
  cin >> Vs;
  if(N==0){
    cout << "0\n";
    return 0;
  }
  vector<ll> V(N);
  vector<vector<ll>> dp(1<<N,vector<ll>(N,4e18));
  for(int i=0;i<N;i++){
    cin >> V[i];
    dp[(1<<i)][i]=abs(Vs-V[i])*(i+1);
  }
  for(int i=0;i<(1<<N);i++){
    for(int j=0;j<N;j++){
      if(dp[i][j]>2e18){continue;}
      for(int k=0;k<N;k++){
        if((i&(1<<k))==0){
          dp[i|(1<<k)][k]=min(dp[i|(1<<k)][k],dp[i][j]+abs(V[j]-V[k])*abs(j-k));
        }
      }
    }
  }
  cout << (*min_element(dp[(1<<N)-1].begin(),dp[(1<<N)-1].end())) << "\n";
  return 0;
}