rt
部分代码

long long c_vis;
int c_u;
bool check(){
	if(w[c_u][b]||c_u==b)
		return 1;
	for(char v=1;v<=n;++v)
		if(w[c_u][v]&&!(1ll<<v&c_vis)){
			c_vis|=1ll<<v;
			char temp=c_u;
			c_u=v;
			if(check())
				return 1;
			c_u=temp;
		}
	return 0;
}
void a_star(){
	struct path{
		long long vis;
		int dis;
		char pth[ruo],total,u;
		bool operator<(const path &temp)const{
			if(dis+h[u][b]!=temp.dis+h[temp.u][b])
				return dis+h[u][b]>temp.dis+h[temp.u][b];
			for(char i=1;i<=total;++i)
				if(pth[i]!=temp.pth[i])
					return pth[i]>temp.pth[i];
			return total>temp.total;
		}
	};
	priority_queue<path>q;
	q.push({1ll<<a,0,{0,(char)a},1,(char)a});
	int cnt=0;
	path x;
	while(q.size()){
		x=q.top();
		q.pop();
		if(x.u==b){
			++cnt;
			if(cnt==k){
				printf("%d",x.pth[1]);
				for(char i=2;i<=x.total;++i)
					printf("-%d",x.pth[i]);
				return;
			}
		}
		++x.total;
		for(char v=1;v<=n;++v)
			if(w[x.u][v]&&!(1ll<<v&x.vis)){
				c_vis=1ll<<v|x.vis;
				c_u=v;
				if(!check())
					continue;
				char temp=x.u;
				x.vis|=1ll<<v;
				x.dis+=w[x.u][v];
				x.pth[x.total]=v;
				x.u=v;
				q.push(x);
				x.u=temp;
				x.vis^=1ll<<v;
				x.dis-=w[x.u][v];
			}
	}
	puts("No");
}

在每次更新路径时，判断是否为无用路径，可以大大优化复杂度。
由于我太蒻了，不会证复杂度，故发此贴（违规紫衫）。