以下、 \(K+1\) を \(K\) と置き直します。

\(N=K\) ならばこの問題は巡回セールスマン問題にほかなりません。よってこのケースでは \(\mathrm{DP}[T][v]\) を「交差点 \(D_j\) のうち通過したものの集合が \(T\) で、交差点 \(v\) にいるときの、自動時間の最小値」とする bitDP により \(O(2^KK^2+M)\) で問題を解くことができます。

（実装上は \(S\) も \(D\) に含めてしまうことで、求める答えを \(\mathrm{DP}[全て][S]\) とすることができます）

元の問題を巡回セールスマン問題に帰着することを考えます。そのためには、 \(S\) 及び \(D_j\) たちの間について最短移動時間がわかればよいです。これは、各頂点を始点としたダイクストラ法を計 \(K\) 回行うことにより、 \(O(KM\log M)\) 時間で求められます。

以上より全体の計算量は \(O(KM\log M+2^KK^2)\) となります。

実装例 (C++)

#include<bits/stdc++.h>
using namespace std;

vector<long long>solve(int s, vector<vector<pair<int,int>>>&G){
  // s を始点とし、各頂点までの最短距離を返す
  int n = G.size();
  vector<long long>dist(n, 1e18);
  dist[s] = 0;
  priority_queue<pair<long long,int>>q;
  q.push({0, s});
  while(q.size() > 0){
    auto[d, v] = q.top(); q.pop();
    d = -d;
    if(d != dist[v]) continue;
    for(auto[vv,c]: G[v]){
      if(dist[vv] > dist[v] + c){
        dist[vv] = dist[v] + c;
        q.push({-dist[vv], vv});
      }
    }
  }
  return dist;
}

int main(){
  int n, m;
  cin >> n >> m;
  vector<vector<pair<int,int>>>G(n);
  for(int i=0; i<m; i++){
    int u, v, w;
    cin >> u >> v >> w;
    u--, v--;
    G[u].push_back({v,w});
    G[v].push_back({u,w});
  }
  int s, k;
  cin >> s >> k;
  vector<int>d(k+1);
  d[0] = s - 1;
  for(int i=1; i<=k; i++){
    int t;
    cin >> t;
    d[i] = t - 1;
  }
  k++;

  vector<vector<long long>>dist(k+1, vector<long long>(k+1));
  for(int i=0; i<k; i++){
    vector<long long>temp = solve(d[i], G);
    for(int j=0; j<k; j++){
      dist[i][j] = temp[d[j]];
    }
  }
  
  // tsp
  vector<vector<long long>>dp(k, vector<long long>(1<<k, 1e18));
  dp[0][0] = 0;
  for(int s=0; s<1<<k; s++){
    for(int i=0; i<k; i++){
      for(int j=0; j<k; j++){
        dp[j][s | (1<<j)] = min(dp[j][s | (1<<j)], dp[i][s] + dist[i][j]);
      }
    }
  }
  cout << dp[0][(1<<k)-1] << endl;
}

実装例 (Python)

import heapq

def solve(s,G):
  # s を始点とし、各頂点までの最短距離を返す
  N = len(G)
  dist = [10**18] * N
  dist[s] = 0
  q = [(0, s)]
  while len(q) > 0:
    d, v = heapq.heappop(q)
    if dist[v] != d:
      continue
    for vv, c in G[v]:
      if dist[vv] > dist[v] + c:
        dist[vv] = dist[v] + c
        heapq.heappush(q, (dist[vv], vv))
  return dist

def main():
  N, M = map(int, input().split())
  G = [[] for _ in range(N)]
  for _ in range(M):
    U, V, W = map(int,input().split())
    U -= 1
    V -= 1
    G[U].append((V, W))
    G[V].append((U, W))
  S, K = map(int, input().split())
  D = [S] + list(map(int, input().split()))
  D = [v-1 for v in D]
  K += 1

  dist = []
  for d in D:
    temp = solve(d, G)
    dist.append([temp[d] for d in D])

  # TSP
  dp = [[10**18] * (1<<K) for _ in range(K)]
  dp[0][0] = 0
  for s in range(1<<K):
    for i in range(K):
      for j in range(K):
        dp[j][s | (1<<j)] = min(dp[j][s | (1<<j)], dp[i][s] + dist[i][j])

  print(dp[0][-1])

main()