首先考虑 \(dp_{i,msk}\) 表示当前连通了 \(msk\) 中所有关键点，并且当前连通的非关键点包含 \(i\) 的最小代价。
然后考虑如何转移。我们先用 \(Floyd\) 预处理所有点对之间的最短路 \(dist_{i,j}\)。同时，每次选取的两个用于合并的关键点集合一定没有交集，所以我们可以直接枚举子集得到转移集合 \(S\) 和 \(msk/S\)。然后枚举转移用的非关键点 \(a\) 和 \(b\) 让 \(i\) 和它们都连通，\(dp_{a,msk}+dp_{b,msk/S}+dist_{i,a}+dist_{i,b}\) 就是答案。一个合法的最优解一定能通过断点的方式每次被划分成 \(dp_{i,msk}\) 的最优解，所以这样也一定能找到最优解。
最后还要合并答案，因为我们只是要给定的点对两两连通，并不需要所有的关键点连通。
我们可以枚举集合划分，被划分到同一个集合中的点对就要求全部连通，否则只要自己连通即可。\(4\) 的集合划分一共 \(15\) 种，我是提前打出划分数组然后枚举答案。 \(15\times2^8n\) 次。
枚举子集是 \(3^k\)，复杂度 \(O(n^23^8)\)，可以通过。
struct index{
map<st,int>mp;
int cnt=0;
inline void ins(string s,int id){
mp[s]=id;
}
inline int qry(string s){
return mp[s];
}
};
int n,m,c,f[35][35],dp[35][1<<8],ans[1<<8],to[4];
st x,y,s[8];
int d[15][4]={{0,0,0,0},{0,0,0,1},{0,0,1,0},{0,0,1,1},
{0,1,0,0},{0,1,0,1},{0,1,1,0},{0,1,1,1},
{0,0,1,2},{0,1,1,2},{0,1,2,2},{0,1,2,3},
{0,1,2,1},{0,1,2,0},{0,1,0,2}};
inline void solve(){
rp(i,n)rp(j,n)f[i][j]=1e9;
rp(i,n)f[i][i]=0;
index idmap;
rp(i,n){
cin>>x;
idmap.ins(x,i);
}rp(i,m){
cin>>x>>y>>c;
int a=idmap.qry(x),b=idmap.qry(y);
f[a][b]=min(f[a][b],c);
f[b][a]=min(f[b][a],c);
}rp(k,n)rp(i,n)rp(j,n)f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
rd(i,4)cin>>s[i]>>s[4+i];
rep(i,1,n)rd(j,(1<<8))dp[i][j]=1e9,ans[j]=1e9;
rep(msk,1,(1<<8)-1)rp(i,n){
int cnt=__builtin_popcount(msk);
if(cnt==1){
int d=__lg(msk&(-msk));
dp[i][msk]=f[i][idmap.qry(s[d])];
ans[msk]=0;
continue;
}
for(int xx=msk-1;xx;xx=(xx-1)&msk){
int yy=(msk^xx);
rp(a,n)rp(b,n){
dp[i][msk]=min(dp[i][msk],dp[a][xx]+dp[b][yy]+f[i][a]+f[i][b]);
}
}
ans[msk]=min(ans[msk],dp[i][msk]);
}
int tans=1e9;
rd(k,15){
int cur=0;
rd(c,4){
int res=0,cans=1e9;
rd(i,4)if(d[k][i]==c)res|=(1<<i),res|=(1<<(4+i));
rep(msk,0,(1<<8)-1)if((msk&res)==res)cans=min(cans,ans[msk]);
cur+=cans;
}tans=min(tans,cur);
}cout<<tans<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
while(n){
solve();
cin>>n>>m;
}
return 0;
}
//Crayan_r
但是这是比较暴力的做法，我们考虑更优一点的做法。
我们还是考虑 \(dp_{i,msk}\)，每个 \(dp_{i,msk}\) 可以往 \(dp_{i,msk\cup S}\) 贡献 \(dp_{i,msk}\)，可以往相邻的边 \(e\) 贡献 \(dp_{b_e,msk}\) 贡献 \(dp_{i,msk}+e.c\)。
这样每次的转移其实就是 \(2^8+n\) 的，会更优一些。
但是这个似乎阶段性不明显，我们发现转移的形式是总和最小值，考虑用 \(Dijkstra\) 进行转移。这样，我们每次提取出当前的 \(dp_{i,msk}\)，枚举转移。点数是 \(O(n2^8)\)，复杂度是 \(O(4^8n\log n)\)。但是仔细分析一下就会发现，有效（可能会更新栈）的转移只有 \(O(3^8n)\) 个，所以实际上的复杂度是 \(O(3^8n\log n+4^8n)\)。
然后考虑合并答案，我们可以记录 \(ans_i\) 表示 \(i\) 集合内的点对都已经满足要求的最小答案。用所有的 \(dp_{j,msk}\) 更新对应的 \(i\)，然后枚举 \(a,b\)，存在转移 \(ans_{a\cup b}=ans_a+ans_b\)。
最后输出 \(ans_{15}\) 即可。
实际跑出来，这个做法快了将近 \(30\) 倍。
int n,m,c,dp[35][256],ans[256];
st x,y,s[8];
vt<pii>vv[35];
map<string,int>id;
inline void solve(){
id.clear();
rp(i,n)vv[i].clear();
rp(i,n){
cin>>x;
id[x]=i;
}rp(i,m){
cin>>x>>y>>c;
int a=id[x],b=id[y];
vv[a].pb({b,c});
vv[b].pb({a,c});
}
rd(i,4)cin>>s[i]>>s[4+i];
rp(i,n)rd(j,256)dp[i][j]=1e9,ans[j]=1e9;
priority_queue<pair<int,pii> >pq;
rd(i,8){
int x=id[s[i]];
dp[x][1<<i]=0;
pq.push({0,{x,1<<i}});
}while(pq.size()){
int x=pq.top().second.first;
int msk=pq.top().second.second;
int val=-pq.top().first;pq.pop();
if(val>dp[x][msk])continue;
rd(y,256){
if(dp[x][msk|y]>dp[x][msk]+dp[x][y]){
dp[x][msk|y]=dp[x][msk]+dp[x][y];
pq.push({-dp[x][msk|y],{x,msk|y}});
}
}for(auto e:vv[x]){
int y=e.first,c=e.second;
if(dp[y][msk]>dp[x][msk]+c){
dp[y][msk]=dp[x][msk]+c;
pq.push({-dp[y][msk],{y,msk}});
}
}
}rp(i,n)rd(msk,256){
int t=0;
rd(j,4)if((msk>>j&1)&&(msk>>(j+4)&1)){
t|=(1<<j);
}ans[t]=min(ans[t],dp[i][msk]);
}rd(i,16)rd(j,16)ans[i|j]=min(ans[i|j],ans[i]+ans[j]);
cout<<ans[15]<<endl;
}
signed main(){
ios::sync_with_stdio(false);
cin.tie(0);
cin>>n>>m;
while(n){
solve();
cin>>n>>m;
}
return 0;
}
//Crayan_r