ABC369E题解

纪念本蒟蒻手搓出的第$n(n\leq114514)$道绿

思路

题目数据有点$尸 \hspace {-.2cm} \tiny{米}$（实在太小了！），注意到每一次询问中$k\leq5$，这就很关键，或者说随便造。这个大小小到我可以把所有要求的边的顺序排列一边外加枚举所有边的正反情况（后面会详细说）在把所有边都访问一边，还只有$1e6$的常数复杂度。

好了，废话说完了，开始正式写题解。

考虑把每一种边的访问顺序枚举一边，一条一条地走，每次从上一条边的终点走到这一条边的起点，再从这条边的起点走到这条边的终点^[1]。这时你巧妙地发现，这个图是无向图！！！所以我们还需要枚举一便每一条边的正反情况 （感谢数据大小的馈赠），然后就这么水灵灵地 （什么破形容词） 做出来这道题了。

AC代码

#include<bits/stdc++.h>
#define int long long
using namespace std;
int fac[6]={0,1,2,6,24,120};
const int N=410,M=2e5+10;
int d[N][N],n,m;
struct node{int x,y,w;}e[M];
int a[10],k;
int check()
{
	int res=1ll<<60;
	for(int s=0;s<(1<<k);s++)
	{
		int now=1,ans=0;
		for(int i=1;i<=k;i++)
		{
			if(s&(1<<i-1))
			{
				ans+=d[now][e[a[i]].x];now=e[a[i]].y;
				ans+=e[a[i]].w;
			}
			else
			{
				ans+=d[now][e[a[i]].y];now=e[a[i]].x;
				ans+=e[a[i]].w;
			}
		}
		res=min(res,ans+d[now][n]);
	}
	return res;
}
signed main()
{
	scanf("%lld%lld",&n,&m);
	memset(d,0x3f,sizeof(d));
	for(int i=1,w;i<=m;i++)
	{
		scanf("%lld%lld%lld",&e[i].x,&e[i].y,&e[i].w);
		d[e[i].x][e[i].y]=d[e[i].y][e[i].x]
		=min(d[e[i].x][e[i].y],e[i].w);
	}
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
		{
			d[i][i]=0; 
			for(int j=1;j<=n;j++)if(j!=i)
				d[i][j]=min(d[i][j],d[i][k]+d[k][j]);
		}
	/*
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)printf("%15lld",d[i][j]);
		puts("");
	}
	*/
	int q;scanf("%lld",&q);
	while(q--)
	{
		scanf("%lld",&k);
		for(int i=1;i<=k;i++)scanf("%lld",&a[i]);
		sort(a+1,a+k+1);
		int ans=check();
		for(int i=1;i<=fac[k];i++)
		{
			next_permutation(a+1,a+k+1);
			ans=min(ans,check());
		}
		printf("%lld\n",ans);
	}
	return 0;
}