本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2024-09-02 08:54:09

思路

看到 $n$ 的范围很小，所以能够用 Floyd 跑出所有点之间的最短路。看到每一次询问，我们将经过 $k$ 条边转化为依次经过 $k+k$ 个点，当然在一条边上的点必须相邻，所以可以将所有的边全排列，并枚举先经过每一条边上的哪一个点，求一个最小值即可。

代码

#include<bits\/stdc++.h>
#define int long long
#define lowbit(x) (x&(-x))
#define faster ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
using namespace std;
struct nd{
	int x,y,z;
}a[200005];
int b[105];
int dp[505][505];
int n,m,q,k;
signed main() {
	faster
	cin>>n>>m;memset(dp,0x3f,sizeof dp);
	for(int i=1;i<=m;i++){
		int x,y,z;
		cin>>x>>y>>z;
		a[i]={x,y,z};
		dp[x][y]=min(dp[x][y],z);
		dp[y][x]=min(dp[y][x],z);
	}
	for(int i=1;i<=n;i++){
		dp[i][i]=0;
	}
	for(int k=1;k<=n;k++){
		for(int i=1;i<=n;i++){
			for(int j=1;j<=n;j++){
				dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]);
			}
		}
	}
	cin>>q;
	for(int i=1;i<=q;i++){
		cin>>k;
		int ans=1e18;
		for(int j=1;j<=k;j++){
			cin>>b[j];
		}sort(b+1,b+1+k);
	    do  {
	    	for(int u=0;u<(1<<k);u++){
	    		\/\/ cout<<1;
	    		int vis[10]={0},o=u;
	    		for(int j=1;j<=k;j++){
	    			if(o&1) vis[j]=1;
	    			o>>=1;
	    		}
	    		int pos=1,sum=0;
	    		for(int j=1;j<=k;j++){
	    			if(vis[j]==0){
	    				sum+=dp[pos][a[b[j]].x]+a[b[j]].z;pos=a[b[j]].y;
	    			}
	    			else {
	    				sum+=dp[pos][a[b[j]].y]+a[b[j]].z;pos=a[b[j]].x;
	    			}
	    		}
	    		ans=min(ans,sum+dp[pos][n]);
	    	}
	    }while(next_permutation(b+1,b+1+k));  
		cout<<ans<<"\n";
	}
	return 0;
}