题解：AT_abc369_e [ABC369E] Sightseeing Tour 详细版

题目大意

给定一个 N N N 个点， M M M 条边的无向图。其中边有边权。有 Q Q Q 次询问，每一次给你 K K K 条必须经过的边（但是方向没有限制），问从 1 1 1 到 N N N 的最短路长度是多少。

思路

观察数据范围，可以发现：虽然 M M M 很大，但是 N N N 和 K K K 并不大。 K ≤ 5 K\le5 K≤5，可以暴力枚举每一条边经过时的方向以及经过它们的顺序。 N ≤ 400 N\le400 N≤400，考虑预处理出任意两点之间的最短路。

我们使用dfs来暴力枚举，首先考虑每条边的方向，再全排列去确定遍历顺序。在每一种具体方案中，我们可以将点之间的最短路相加，并且加上边权，得出这种方案的最短路径长度，再取最小值即可。

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>
#include <cstring>
using namespace std;
typedef long long LL;

int n, m, q, k;
int a[40], b[40];
LL ans; // 答案
int A[400010]; // 边
int B[400010]; // 边
int C[400010]; // 边
LL dis[810][810]; // 最短路
int vis[810][810]; // 标记

struct edge // 边
{
	int y, w;
} ;

vector<edge> g[810]; // 图

void add(int x, int y, int w) // 建边
{
	g[x].push_back((edge){y, w});
}

struct node // 点
{
	int x; // 编号
	LL d; // 距离起点的最短路
	
	bool operator < (const node & b) const // 重载运算符
	{
		return d > b.d;
	}
} ;

void dijkstra(int s) // 最短路
{
	priority_queue<node> q;
	memset(dis[s], 0x3f, sizeof(dis[s]));
	memset(vis[s], 0, sizeof(vis[s]));
	q.push((node){s, 0});
	dis[s][s] = 0;
	while (q.size())
	{
		int x = q.top().x;
		q.pop();
		if (vis[s][x])
			continue;
		vis[s][x] = 1;
		for (int i = 0; i < g[x].size(); i++)
		{
			int y = g[x][i].y;
			int w = g[x][i].w;
			if (dis[s][y] > dis[s][x] + w)
			{
				dis[s][y] = dis[s][x] + w;
				q.push((node){y, dis[s][y]});
			}
		}
	}
}

void solve(int step) // 暴力枚举
{
	if (step > k)
	{
		for (int i = 1; i <= k; i++)
			b[i] = i;
		do
		{
			LL sum = dis[1][A[a[b[1]]]];
			for (int i = 2; i <= k; i++)
				sum += C[a[b[i - 1]]] + dis[B[a[b[i - 1]]]][A[a[b[i]]]];
			sum += C[a[b[k]]] + dis[B[a[b[k]]]][n];
			ans = min(ans, sum);
		} while (next_permutation(b + 1, b + k + 1)); // 全排列
		return ;
	}
	swap(A[a[step]], B[a[step]]); // 边的方向
	solve(step + 1);
	swap(A[a[step]], B[a[step]]); // 边的方向
	solve(step + 1);
}

int main()
{
	cin >> n >> m;
	for (int i = 1; i <= m; i++)
	{
		int x, y, w;
		cin >> x >> y >> w;
		add(x, y, w);
		add(y, x, w);
		A[i] = x;
		B[i] = y;
		C[i] = w;
	}
	for (int i = 1; i <= n; i++)
		dijkstra(i);
	cin >> q;
	while (q--)
	{
		cin >> k;
		for (int i = 1; i <= k; i++)
			cin >> a[i];
		ans = 9e18; // 不要忘记初始值
		solve(1);
		cout << ans << endl;
	}
	return 0;
}