RT

不知道为什么 MLE 3 个点。

据说 A* 最好可以做到 90 分。。求dalao帮忙调一下QAQ

还是说我 bfs 写的太丑了？

#include <bits/stdc++.h>
#define ll long long
using namespace std;
int i,j,k,n,m,s,t;
void read(int &x){
	char c;x=0;int b=1;do{c=getchar();if(c==45)b=-1;}while(c>57||c<48);
	do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);x*=b;
}
void read(ll &x){
	char c;x=0;int b=1;do{c=getchar();if(c==45)b=-1;}while(c>57||c<48);
	do x=x*10+c-48,c=getchar();while(c<=57&&c>=48);x*=b;
}
struct edge{
	int next,to,w;
}a[100010],L[100010];
int head[10010],len;
void add(int x,int y,int z){
	a[++len]=(edge){head[x],y,z};
	head[x]=len;
}
int vis[100010],dis[100010];
void dij(){
	priority_queue<pair<int,int> >Q;
	Q.push(make_pair(0,t));
	memset(dis,0x3f,sizeof(dis));
	dis[t]=0;
	while(!Q.empty()){
		int now=Q.top().second;
		Q.pop();if(vis[now])continue;vis[now]=1;
		for(int i=head[now];i;i=a[i].next){
			int u=a[i].to;
			if(dis[now]+a[i].w<=dis[u]){
				dis[u]=dis[now]+a[i].w;
				Q.push(make_pair(-dis[u],u));
			}
		}
	}
}
typedef pair<pair<int,vector<int> >,pair<int,map<int,int> > > PAIR;
int cnt;
vector<int>V1,V;
map<int,int>M1,M;
void Astar(){
	priority_queue<PAIR>Q;
	vector<int>V1;map<int,int>Q1;
	V1.push_back(-s);Q1[s]=1;
	Q.push(make_pair(make_pair(0,V1),make_pair(-s,Q1)));
	while(!Q.empty()){
		int now=-Q.top().second.first,S=-Q.top().first.first;
		V1=Q.top().first.second;
		M1=Q.top().second.second;
		Q.pop();
		if(now==t){
			++cnt;
			if(cnt==k){
				V=V1;
				for(int i=0;i<V.size();i++){
					cout<<-V[i];
					if(i!=V.size()-1)cout<<"-";
				}
				exit(0);
			}
			continue;
		}
		for(int i=head[now];i;i=a[i].next){
			int u=a[i].to;
			V=V1;M=M1;
			if(M[u])continue;
			V.push_back(-u);M[u]=1;
			Q.push((PAIR){make_pair(-(S+a[i].w-dis[now]+dis[u]),V),make_pair(-u,M)});
		}
	}
}
int main() {
	cin>>n>>m>>k>>s>>t;
	for(i=1;i<=m;i++){
		int x,y,z;
		read(x);read(y);read(z);
		add(y,x,z);
	}
	dij();
	len=0;
	for(i=1;i<=n;i++){
		for(int j=head[i];j;j=a[j].next){
			int u=a[j].to,w=a[j].w;
			L[++len]={i,u,w};
		}
	}
	memset(head,0,sizeof(head));len=0;
	for(i=1;i<=m;i++){
		add(L[i].to,L[i].next,L[i].w);
	}
	Astar();
	cout<<"No"<<endl;
	//cerr << 1.0*clock()/CLOCKS_PER_SEC << endl;
	return 0;
}