abc369E Sightseeing Tour

有N个岛和M座双向桥，编号为i的桥连接岛U[i]和V[i]，过桥耗时T[i]，桥连接两不同的岛屿，两个岛之间可能会有多座桥。
有Q组询问，每次询问给出K座桥，问从1号岛到N号岛的最少耗时，要求给出的K座桥分别至少经过1次。
2<=N<=400; N-1<=M<=2E5; 1<=U[i]<V[i]<=N; 1<=T[i]<=1E9; 1<=Q<=3000; 1<=K[i]<=5;

分析：跑floyd求出任意两岛之间的最短耗时，然后枚举所有可能的路径，即对K座桥全排列，并枚举桥的两端谁做入口谁做出口，将"1-桥-N"串起来得到耗时，取最小值。

#include <bits/stdc++.h>
using i64 = long long;

const i64 inf = 1E18;
i64 d[405][405];

void solve() {
	int N, M;
	std::cin >> N >> M;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) {
				d[i][j] = 0;
			} else {
				d[i][j] = inf;
			}
		}
	}

	std::vector<std::tuple<int,int,int>> edges(M+1);
	for (int i = 1; i <= M; i++) {
		int u, v;
		i64 t;
		std::cin >> u >> v >> t;
		edges[i] = {u, v, t};
		d[u][v] = std::min(d[u][v], t);
		d[v][u] = std::min(d[v][u], t);
	}

	for (int k = 1; k <= N; k++) {
		for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				d[i][j] = std::min(d[i][j], d[i][k] + d[k][j]);
			}
		}
	}

	auto getb = [&](const std::vector<int> &v, int st, i64 &w) {
		std::vector<int> res;
		for (size_t i = 0; i < v.size(); i++) {
			int x, y, z;
			std::tie(x, y, z) = edges[v[i]];
			if (st & (1 << i)) {
				res.push_back(y);
				res.push_back(x);
			} else {
				res.push_back(x);
				res.push_back(y);
			}
			w += z;
		}
		return res;
	};

	int Q;
	std::cin >> Q;
	for (int i = 1; i <= Q; i++) {
		int K;
		std::cin >> K;
		std::vector<int> B(K);
		for (auto &x : B) {
			std::cin >> x;
		}
		std::sort(B.begin(), B.end());

		i64 ans = inf;
		do {
			for (int j = 0; j < (1 << K); j++) {
				i64 res = 0;
				auto b = getb(B, j, res);
				res += d[1][b.front()] + d[b.back()][N];
				for (size_t k = 2; k < b.size(); k += 2) {
					res += d[b[k]][b[k-1]];
				}
				ans = std::min(ans, res);
			}
		} while (std::next_permutation(B.begin(), B.end()));
		std::cout << ans << "\n";
	}
}

int main() {
	std::cin.tie(0)->sync_with_stdio(0);
	int t = 1;
	while (t--) solve();
	return 0;
}