#include <iostream> #include <vector> #include <queue> #include <deque> #include <limits> #include <algorithm> using namespace std; const int INF = numeric_limits<int>::max()>>1; typedef pair<int,int> PII; int boarding_fee; int k; vector<vector<int>> dist; int nrsubsets; vector<PII> subsets; void read_dijkstra(); void generate_subset_costs(); int main() { read_dijkstra(); generate_subset_costs(); vector<int> dp(1<<k,INF); dp[0]=0; for(int i=0;i<(1<<k);++i) for(int j=0;j<nrsubsets;++j){ int s=subsets[j].first; if((i&s) == 0) dp[i|s] = min(dp[i|s],dp[i]+subsets[j].second); } cout<<dp[(1<<k)-1]<<'\n'; } void read_dijkstra() { int n,m; cin>>n>>m; vector< vector<PII> > Adj(n+1); for(int i=0;i<m;++i){ int t,u,v,c; cin>>t>>u>>v>>c; Adj[u].push_back(PII(v,c)); if(t==2) Adj[v].push_back(PII(u,c)); } int comp_ind; cin>>boarding_fee>>comp_ind>>k; vector<int> vempl(k+1); for(int i=1;i<=k;++i) cin>>vempl[i]; vempl[0]=comp_ind; dist.resize(k+1,vector<int>(k+1,0)); for(int i=0;i<=k;++i){ int st=vempl[i]; vector<int> d(n+1,INF); priority_queue<PII,deque<PII>,std::greater<PII>> pq; pq.push(PII( d[st]=0 , st )); while(!pq.empty()){ int c=pq.top().first; int v=pq.top().second; pq.pop(); if(d[v]==c) for(auto it=Adj[v].begin();it!=Adj[v].end();++it) if(d[it->first] > c + it->second) pq.push(PII((d[it->first]=c+it->second) , it->first)); } for(int j=0;j<=k;++j) dist[i][j]=d[vempl[j]]; } } void generate_subset_costs() { vector<int> cst(1<<k,INF); for(int i1=1;i1<=k;++i1) for(int i2=1;i2<=k;++i2) for(int i3=1;i3<=k;++i3) for(int i4=1;i4<=k;++i4){ int ind = (1<<(i1-1))|(1<<(i2-1))|(1<<(i3-1))|(1<<(i4-1)); int d = dist[0][i1]+dist[i1][i2]+dist[i2][i3]+dist[i3][i4]; cst[ind] = min(cst[ind],d); } nrsubsets=0; for(int i=0;i<(1<<k);++i) if(cst[i]!=INF) ++nrsubsets; subsets.resize(nrsubsets); int c=0; for(int i=0;i<(1<<k);++i) if(cst[i]!=INF) subsets[c++] = PII(i,cst[i]+boarding_fee); }