前言

Astar 又回来（活过来）啦！

先别急着说，Astar 肯定会被卡掉的啊，不可能过的。

来，先读完你再说。

估计有 99.9% 的可能不会被卡掉，如果被卡掉的话请在评论区留言或私信。

本文有一些非常巧妙的变换可以转成普通模型的时间复杂度。

注意：本题的证明会涉及到 dijkstra 的算法本质，所以若还没有了解（只会打模板的），请先去了解。

普通的 Astar 做法

很多人就是没认真看题，然后随便看了看，发现：这不就是 $K$ 短路吗？

不不不。这道题还多了一个限制：每一个点只能走一次，且输出路径要按照字典序输出。

于是有一些人便在这个代码上面改了改，就提交了上去。

学过 A* 算法的你肯定知道 A* 的估价函数是 $f(i)=g(i)+h(i)$，其中 $g(i)$ 是从起点 $s$ 到 $i$ 的路径长度，而 $h(i)$ 是从点 $i$ 到终点 $t$ 的预估路径长度。

也就是说，A* 算法的时间复杂度优劣就看预估函数的质量和消耗的时间了。

在没有前面的每一个点只能走一次这个条件的情况下，A* 的时间复杂度最坏为 $\mathcal O(kn \log n)$。

可是，如果加上这个条件，然后再套用以前的 A* 算法，你会发现，你的预估函数 $h(i)$ 和真实的最短路径函数 $true(i)$ 差了非常多。

这样的话，可以构造一组数据使得你的程序出现各种奇怪的错误。

先放这个方法的代码：[错误方法的代码。]

我们来看到提交记录：

发现存在一组数据能够将我们 Hack 掉。

考虑其他方法：我们可不可以用预处理出从 $t \to i$ 的最短路，使得这条路径上没有任何一个点是重复的吗？

显然，Hack 方法与上面一致，让你尽可能的经过环或者是尽可能经过重复的边即可。

那我们该怎么办呢？设计不出来一个好的预估算法，我们就做不出来这道题了。

这个时候，我们就需要跳出平常的思维了。

不寻常的思维

发现如果时间复杂度是 $\mathcal O(kn \log n)$，运算量大概只有 $3000000$（乘上字符串比较的常数），有点太少了。

考虑能否可以不进行预处理，直接需要什么就计算什么即可。

这样子的话，我们就可以设计出一个函数，求出从终点开始，不经过哪些点且不重复经过点的最短路。

时间复杂度就是平常的，$\mathcal O(n \log n)$，当然还会更短（因为有很多点无法经过）。

然后，我们可以对于每一个点在扩展的时候都做一次这个函数求出我们需要的信息，时间复杂度为 $\mathcal O(kn^2 \log n^2)$，化简之后就是 $\mathcal O(pkn^2 \log n)$，$p$ 是字符串比较的常数。

能通过吗？大概计算一下计算量最坏为 $1.5 \times 10^8$，且还跑不满，可以通过此题。

我们来试图证明一下这个算法的正确性（当然，我并不会严谨的证明）。

首先，我们求一般模型的 $k$ 短路的最坏时间复杂度为 $\mathcal O(kn \log n)$。

发掘一下一般模型（普通 $K$ 短路）用 A* 求解有哪一些性质：

• 首先，预处理出的从终点 $t$ 到某一个点 $i$ 的最短路是实际可行的。
• 预处理的最短路是最短的，貌似是一句废话。
• 所有结点的子结点的搜索代价值 $V>0$。

首先，显然的，第 $3$ 条肯定满足。

我们是在实际需求的情况下去求解最短路的，也就是说求出来的最短路肯定是可以和当前的路径接上去的（根据前面的定义得出）。

所以第 $1$ 条满足，当然第 $2$ 条是满足的（不是预处理的，是实时计算的）。

所以该算法的时间复杂度为 $\mathcal O(kn^2 \log n)$。

本题就做完了，我会在结尾放上代码。

证明部分

Part 1

首先，考虑一个点 $z$ 的最短路如何更新。

假设有一条当前到 $x$ 的最短路径 $A$ 和一条到 $x$ 的次短路径 $B$（不严格的）。

然后，假设 $A$ 路径经过了的点与 $B$ 路径经过的点不一样（一样的话就不用证明了）。

假设 $x \ne z$。

显然，分讨几种情况：

1. 点 $z$ 不在 $A,B$ 任何一条路径当中。
2. 点 $z$ 在 $A$ 路径中，不在 $B$ 路径中。
3. 点 $z$ 不在 $A$ 路径中，但在 $B$ 路径中。
4. 点 $z$ 在 $A,B$ 两条路径当中。

显然，对于第一种情况，显然成立。

第二种情况，显然，$B$ 路径已经比 $A$ 长了，肯定也成立。

第三种情况，根据 dijkstra 的算法流程，若存在一条更短的路径从 $A$ 路径的终点 $x$ 继续延伸到 $z$ 的话，那么就不会先更新 $z$ 这个点。

但是，因为 $z$ 在 $B$ 路径中且不是终点，而且延伸出了 $B$ 路径的后半部分，所以可以判断出 $z$ 的最短路已经确定，所以无法用 $A$ 路径更新 $z$，但是 $B$ 路径已经更新了 $z$。

我们在设计这个算法的时候，只是说点 $x$ 只管最短路径是什么，不管其他的次短路。没有说在遍历 $z$ 点的时候，$B$ 路径不能到 $z$ 点去更新啊！再说，$z$ 点确定的时候都还没有 $A$ 路径呢！

所以，也成立。

第四种情况，直接用 $A$ 或 $B$ 路径从起点 $s$ 到 $z$ 的最短路去更新即可。显然也成立。

所以，证毕，只需保留最短路径即可。

常数优化

上面的常数确实是有一点不堪了，我们来尝试优化一下常数。

但是，我们就需要多证一个东西。

证明：最短路不会走环路

题目已经说了，是正权图，不可能存在负环。

所以，你只要走了一遍环，那么你走的路程就会更长。

若我们从 $x$ 走到了 $x$（绕了一个环），再从 $x$ 走到了终点 $t$，不如直接 $x \to t$，这个地方的证明比较简单，若还无法理解，建议先学习最短路的算法核心部分。

但是注意：$K$ 短路是有可能走环的。

他有可能会在先前路径上多走几个环，来使得该长度不等于最短路径长度但是又只多一点的这种效果。

这就是说为什么 $K$ 短路需要判断是否走了重复的点的原因。

代码如下：正解代码。

#include<bits/stdc++.h>
#define x0 x_0
#define x1 x_1
#define y0 y_0
#define y1 y_1
#define yn y_n
#define d0 d_0
#define d1 d_1
#define j0 j_0
#define j1 j_1
#define k0 k_0
#define k1 k_1
#define LL long long
#define LD long double
using namespace std;
int n,m,k,a,b;
struct node{
	int v;
	LL w;
	bool operator < (const node &o)const{
		return w>o.w;
	}
};
struct dij_node{
	int v;
	LL w;
	bool operator < (const dij_node &o)const{
		return w>o.w;
	}
};
struct STRING{
	char p[50];
	int l;
	bool operator > (const STRING &o)const{
		int cst=min(l,o.l);
		for(int i=0;i<cst;++i){
			if(p[i]>o.p[i]) return 1;
			else if(p[i]<o.p[i]) return 0;
		}
		if(l>=o.l) return 1;
	}
};
struct point{
	int v;
	LL g,h;
	STRING s;
	LL S;
	bool operator < (const point &o)const{
		if((g+h)^(o.g+o.h)) return g+h>o.g+o.h;
		return s>o.s;
	}
};
vector<node> G[60],G2[60];
char inc[60];
int decc[128];
char incode_int(int x){
	return (x<=26 ? 'A'+x-1 : 'a'-26+x-1);
}
int decode_char(char x){
	return (x>='A' && x<='Z' ? x-'A'+1 : x-'a'+27);
}
LL dis[60];
bool f[60];
const LL mex=1e15;
void dijkstra(int s,LL SSS){ // Part 1 部分
	for(int i=1;i<=n;++i) dis[i]=mex;
	dis[s]=0;
	memset(f,0,sizeof(f));
	priority_queue<dij_node> q;
	q.push({s,0});
	while(q.size()){
		dij_node dt=q.top();
		q.pop();
		if(f[dt.v]) continue;
		int x=dt.v;
		f[x]=1;
		for(int i=0;i<(int)G2[x].size();++i){
			int u=G2[x][i].v;
			if(SSS&(1LL<<u)) continue;
			LL w=G2[x][i].w;
			if(dis[u]>dis[x]+w){
				dis[u]=dis[x]+w;
				q.push({u,dis[u]});
			}
		}
	}
	return ;
}
int cnt[60];
void Astar(int s,int t,int k){
	memset(cnt,0,sizeof(cnt));
	priority_queue<point> q;
	STRING psh;
	psh.p[psh.l++]=incode_int(s);
	q.push({s,0,0,psh,1LL<<s});
	while(q.size()){
		point dt=q.top();
		q.pop();
		int x=dt.v;
		++cnt[x];
		if(x==t && cnt[x]==k){
			int len=dt.s.l;
			cout<<decc[dt.s.p[0]];
			for(int i=1;i<len;++i) cout<<"-"<<decc[dt.s.p[i]];
			cout<<"\n";
			exit(0);
		}
		dijkstra(t,dt.S);
		for(int i=0;i<(int)G[x].size();++i){
			int u=G[x][i].v;
			LL w=G[x][i].w;
			if(dt.S&(1LL<<u)) continue;
			dt.s.p[dt.s.l++]=inc[u];
			q.push((point){u,dt.g+w,dis[u],dt.s,dt.S|(1LL<<u)});
			--dt.s.l;
		}
	}
	cout<<"No\n";
	exit(0);
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m>>k>>a>>b;
	for(int i=1;i<=m;++i){
		int u,v;
		LL w;
		cin>>u>>v>>w;
		G[u].push_back({v,w});
		G2[v].push_back({u,w});
	}
	for(int i=1;i<=52;++i) inc[i]=incode_int(i);
	for(int i=0;i<128;++i) decc[i]=decode_char((char)i);
	dijkstra(b,0);
	if(dis[a]>=mex) cout<<"No\n",exit(0);
	Astar(a,b,k);
	return 0;
}

50分的搜索代码

思路：暴力枚举每一条路径，对路径排序后输出第k条。为优化空间和时间，当当前找到的路径总数小于等于k时，将路径存入数组并排序；若超过k，则保留前k条路径。同时记录第k条路径的长度，若未到终点且长度大于当前第k条路径长度，则放弃搜索。

//50分的搜索代码
//思路：暴力枚举每一条路径，在对最终得出的路径排序，输出第k条
//但很明显，不仅会爆时间，若开个结构体数组存储路径，空间也必爆
//所以对于当前路径R，若目前找到的路径总数小于等于k，则放入数组中，排序一遍
//若已找到的路径数大于k，就将其放入k+1位，排序，len--，就排除掉加入这条路径后无贡献的路径了
//对于优化时间，可以记录当前路径中第k条的长度，若未到终点便大于当前第k路径的长度，则这条路径已无贡献，可放弃搜索 
#include<bits/stdc++.h>
using namespace std;
const int N=600;
typedef long long ll;
struct edge{ll x,y,c;int pre;}a[N*5];
int alen,last[N*2];
void ins(ll x,ll y,ll c){
	a[++alen]={x,y,c,last[x]};last[x]=alen;
}
ll read(){
	ll x=0,f=1;char ch=getchar();
	for(;ch<'0'||ch>'9';ch=getchar()) if(ch=='-') f=-1;
	for(;ch<='9'&&ch>='0';ch=getchar()) x=(x<<3)+(x<<1)+ch-'0';
	return x*f;
}
int len=0;
ll n,m,K,st,ed;
struct way{int road[52];ll dis;int siz;}plan[112000];
bool v[600];
ll maxx;
bool cmp(way x,way y){
	if(x.dis!=y.dis) return x.dis<y.dis;
	else{
		for(int i=1;i<=min(x.siz,y.siz);i++){
			if(x.road[i]!=y.road[i]) return x.road[i]<y.road[i];
		}
		return x.siz<y.siz;
	}
}
void dfs(int x,string str,ll dis){
	if(len>=K&&maxx<dis) return ;
	if(x==ed){
		len++;plan[len].dis=dis;
		while(str.size()){
			plan[len].road[++plan[len].siz]=str[0]-'0'+48;
			str.erase(0,1);
		}
		sort(plan+1,plan+len+1,cmp);
		if(len>K){
			plan[len--].siz=0;
		}
		maxx=plan[len].dis;
		return ;
	}
	v[x]=1;
	for(int k=last[x];k;k=a[k].pre){
		int y=a[k].y;
		if(v[y]) continue;
		str.push_back(char(y));
		dfs(y,str,dis+a[k].c);
		str.pop_back();
	}
	v[x]=0;
}

int main(){
	n=read(),m=read(),K=read(),st=read(),ed=read();
	for(int i=1;i<=m;i++){
		ll x=read(),y=read();
		ll c=read();ins(x,y,c);
	}
	string str;str.push_back(char(st));
	dfs(st,str,0);
	if(len<K) puts("No");
	else{
		sort(plan+1,plan+1+len,cmp);
		for(int i=1;i<plan[K].siz;i++){
			printf("%d-",plan[K].road[i]);
		}
		printf("%d\n",plan[K].road[plan[K].siz]);
	}
}

100分的代码

思路：改进50分方法，通过二分法确定第k短路的距离范围。先以终点ed为起点跑最短路，得到每个点到ed的距离；再二分距离limit，判断是否存在至少k条路径总距离≤limit，找到最小limit后，搜索该范围内第k条路径。

//100分的代码
//是50分的代码的改进，对于上一份代码，是用了距离来剪枝，可以想到，我们能先找出第k条路径在哪个距离内再求答案 
//排序，第几个，可以想到二分去求出答案所在的距离范围
//具体的，对于当前路径，可以统计出当前路径长度为dis,设二分路径长度为limit。
//对于在当前点后扩展出来的点，以ed为起点跑最短路， 到这个点，如果最短路+dis<=limit，就说明这条路径合法，路径数就++
//当路径数大于等于k时，说明以当前距离为答案范围，可求出第k短路
//求最短路，观察到n很小，m较大，所以可以用O(n^2)的dijkstra
//求出答案在哪个范围内时，再跑一遍类似的搜索去找路径，记录路径 
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=500;
bool vis[N],bk[N];
int d[N],road[N][N],c[N][N];
int len,cnt;
int n,m,K,st,ed;
void dij(int start){
	memcpy(vis,bk,sizeof(vis));
	memset(d,0x3f,sizeof(d));
	d[start]=0;
	for(int i=1;i<=n;i++){
		int y=-1,mn=INT_MAX;
		for(int j=1;j<=n;j++){
			if(!vis[j]&&mn>d[j]) y=j,mn=d[j];
		}
		if(y==-1) break;
		vis[y]=1;
		for(int j=1;j<=n;j++){
			if(d[j]>d[y]+road[y][j]){
				d[j]=road[y][j]+d[y];
			}
		}
	}
}

bool solve(int x,int limit){
	if(x==ed){
		return ++len>=K;
	}
	dij(ed);
	int howlong[N];memcpy(howlong,d,sizeof(howlong));
	for(int i=1;i<=n;i++){
		if(!bk[i]&&limit>=c[x][i]+howlong[i]){
			bk[i]=1;
			if(solve(i,limit-c[x][i]))
			return 1;
			bk[i]=0;
		}
	}
	return 0;
}
int path[N];
bool get_ans(int x,int limit,int id){
	if(x==ed){
		path[++id]=x;
		if(!limit){
			len=id;
			return !cnt;
		}
		return 0;
	}
	dij(ed);
	path[++id]=x;
	int howlong[N];memcpy(howlong,d,sizeof(howlong));
	for(int i=1;i<=n;i++){
		if(!bk[i]&&limit>=c[x][i]+howlong[i]){
			bk[i]=1;
			if(get_ans(i,limit-c[x][i],id))
			return 1;
			bk[i]=0;
		}
	}
	return 0;
}
int main(){
	memset(road,0x3f,sizeof(road));
	memset(c,0x3f,sizeof(c));
	scanf("%d%d%d%d%d",&n,&m,&K,&st,&ed);
	for(int i=1;i<=m;i++){
		int x,y,f;scanf("%d%d%d",&x,&y,&f);
		road[y][x]=c[x][y]=f;
	}
	int l=0,r=1e9,ans=-1;
	while(l<r){
		int mid=l+r>>1;
		len=0;memset(bk,0,sizeof(bk));
		if(solve(st,mid)) r=mid;
		else{
			ans=mid;
			l=mid+1;
			cnt=K-len;
		}
	}
	len=0;memset(bk,0,sizeof(bk));
	get_ans(st,ans+1,0);
	if(cnt) puts("No");
	else{
		for(int i=1;i<len;i++){
			printf("%d-",path[i]);
		}
		printf("%d",path[len]);
	}
}