观光旅游 题解

我们可以预处理出两两之间的最短距离，枚举经过桥的顺序以及先到达桥的哪一端，模拟即可。

#include <iostream>
#include <cstdio>
#include <memory.h>
#include <algorithm>
#define int long long
using namespace std;
int x[200005], y[200005], z[200005];
int dis[405][405];
int n, m, q, k;
int b[5];
int tmp[5];
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0), cout.tie(0);
	cin >> n >> m;
	memset(dis, 63, sizeof(dis));
	for(int i = 1; i <= n; i++){
		dis[i][i] = 0;
	}
	for(int i = 1; i <= m; i++){
		cin >> x[i] >> y[i] >> z[i];
		dis[x[i]][y[i]] = dis[y[i]][x[i]] = min(dis[x[i]][y[i]], z[i]);
	}
	for(int k = 1; k <= n; k++){
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	cin >> q;
	while(q--){
		cin >> k;
		for(int i = 0; i < k; i++) cin >> b[i];
		for(int i = 0; i < k; i++) tmp[i] = i;
		int ans = 0x3f3f3f3f3f3f3f3fll;
		do{
			for(int i = 0; i < (1 << k); i++){
				int cur = 1, val = 0;
				for(int j = 0; j < k; j++){
					if(i >> j & 1){
						val += dis[cur][x[b[tmp[j]]]];
						val += z[b[tmp[j]]];
						cur = y[b[tmp[j]]];
					}else{
						val += dis[cur][y[b[tmp[j]]]];
						val += z[b[tmp[j]]];
						cur = x[b[tmp[j]]];
					}
				}
				val += dis[cur][n];
				ans = min(ans, val);
			}
		}while(next_permutation(tmp, tmp + k));
		cout << ans << '\n';
	}

	return 0;
}

时间复杂度：$O(n^3+qk!2^k)$。