本問題は以下の \(2\) つの問題を組み合わせることで解くことができます。

• 最短経路問題 … 参考
• 巡回セールスマン問題 … 参考

便宜上、 \(C_{K+1}=1,C_{K+2}=N\) であるとします。
前者について、ダイクストラ法で以下の配列を作成します。

• \(d_{i,j} = C_i\) から \(C_j\) まで到達する最短経路の長さ

後者について、巡回セールスマン問題を以下の bitDP の形で解きます。

• \(dp[S][v] = \{\) 既に訪問した頂点の集合が \(S\) で、現在いる頂点が \(v\) である場合の最小の移動距離 \(\}\)

bitDP を \(1\) からの距離で初期化し、 bitDP の結果に \(N\) までの距離を適切に足すことで \(K\) 要素で bitDP が行えます。

全体として、時間計算量 \(O(K(N+M) \log N + 2^KK^2)\) で本問題に正解できます。

実装例 (C++):

#include<bits/stdc++.h>

using namespace std;
using ll=long long;
using pl=pair<ll,ll>;
using Graph=vector<vector<pl>>;

vector<ll> dijkstra(ll v,Graph &g){
  ll n=g.size();
  vector<ll> d(n,4e18);
  priority_queue<pl,vector<pl>,greater<pl>> pq;
  d[v]=0;
  pq.push({d[v],v});
  while(!pq.empty()){
    auto [cd,v]=pq.top(); pq.pop();
    if(d[v]!=cd){continue;}
    for(auto [nv,w] : g[v]){
      if(d[nv]>d[v]+w){
        d[nv]=d[v]+w;
        pq.push({d[nv],nv});
      }
    }
  }
  return d;
}

int main(){
  ll N,M,K;
  cin >> N >> M >> K;
  Graph g(N);
  for(ll i=0;i<M;i++){
    ll u,v,w;
    cin >> u >> v >> w;
    u--; v--;
    g[u].push_back({v,w});
    g[v].push_back({u,w});
  }
  vector<ll> C(K);
  for(ll i=0;i<K;i++){
    cin >> C[i];
    C[i]--;
  }
  C.push_back(0);
  C.push_back(N-1);
  vector<vector<ll>> sg(K+2,vector<ll>(K+2));
  for(ll i=0;i<K+2;i++){
    auto d=dijkstra(C[i],g);
    for(ll j=0;j<K+2;j++){
      sg[i][j]=d[C[j]];
    }
  }
  vector<vector<ll>> dp(1ll<<K,vector<ll>(K,4e18));
  for(ll i=0;i<K;i++){
    dp[(1ll<<i)][i]=sg[K][i];
  }
  ll res=4e18;
  for(ll i=0;i<(1ll<<K);i++){
    for(ll j=0;j<K;j++){
      if(dp[i][j]>2e18){continue;}
      for(ll k=0;k<K;k++){
        if(i&(1ll<<k)){continue;}
        dp[i|(1ll<<k)][k]=min(dp[i|(1ll<<k)][k],dp[i][j]+sg[j][k]);
      }
    }
  }
  for(ll i=0;i<K;i++){
    res=min(res,dp[(1ll<<K)-1][i]+sg[i][K+1]);
  }
  cout << res << "\n";
  return 0;
}