この問題は以下の \(2\) つのパートに分けられます。

• 全ての \(2\) 頂点間について、それらの距離を求める。
• 距離が最小となる順路を求める。

前者はワーシャルフロイド法を利用することで求めることができます。

• ワーシャル–フロイド法 (Wikipedia)
• 素人によるワーシャルフロイド法
• ワーシャル・フロイド法での全点対最短経路を求めるアルゴリズム

後者は巡回セールスマンに対する bitDP を用いて解くことができます。

• 「bitDPで巡回セールスマンを解く」の解説がよくわからなかったのでさらに解説【python実装】
• ビットDP(bit DP)の考え方 ~集合に対する動的計画法~
• bitDPで巡回セールスマン問題を解いてみる

時間計算量は \(O(N^3+2^KK^2)\) 、空間計算量は \(O(N^2 + 2^KK)\) です。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;

const ll big=1e18;

int main(){
  ll n,m;
  cin >> n >> m;
  vector<vector<ll>> d(n+1,vector<ll>(n+1,big));
  for(ll i=1;i<=n;i++){ d[i][i]=0; }
  for(ll i=0;i<m;i++){
    ll u,v,w;
    cin >> u >> v >> w;
    d[u][v]=min(d[u][v],w);
  }
  for(ll k=1;k<=n;k++){
    for(ll i=1;i<=n;i++){
      for(ll j=1;j<=n;j++){
        d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
      }
    }
  }

  ll s,k;
  cin >> s >> k;
  vector<ll> t(k);
  for(ll i=0;i<k;i++){ cin >> t[i]; }

  vector<vector<ll>> dp(1ll<<k,vector<ll>(k,big));
  for(ll i=0;i<k;i++){
    dp[(1ll<<i)][i]=d[s][t[i]];
  }
  for(ll i=0;i<(1ll<<k);i++){
    for(ll j=0;j<k;j++){
      if(dp[i][j]>=big){continue;}
      for(ll p=0;p<k;p++){
        if(i&(1ll<<p)){continue;}
        dp[i|(1ll<<p)][p]=min(dp[i|(1ll<<p)][p],dp[i][j]+d[t[j]][t[p]]);
      }
    }
  }

  ll res=big;
  for(ll i=0;i<k;i++){
    res=min(res,dp[(1ll<<k)-1][i]+d[t[i]][s]);
  }
  if(res==big){
    cout << "-1\n";
    return 0;
  }
  cout << res << "\n";
  return 0;
}