70分 WA 求条

#include<bits/stdc++.h>
#define N 55
using namespace std;
struct dij_node{
	int u,step;
	bool operator < (const dij_node &opt) const{
		return step > opt.step;
	}
};
struct edge{
	int v,w;
};
struct astar_node{
	int u,step,f;
	string path;
	bool operator < (const astar_node &opt) const{
		if(f == opt.f){
			return path > opt.path;
		}
		return f > opt.f;
	}
};
int n,m,k,s,t,dis[N];
bitset<N> vis;
priority_queue<dij_node> q;
priority_queue<astar_node> pq;
vector<edge> g[N];
void dijkstra(int s){
	memset(dis,0x3f,sizeof dis);
	dis[s] = 0;
	q.push({s,0});
	while(q.empty() == false){
		dij_node now = q.top();
		q.pop();
		int u = now.u;
		if(dis[u] != now.step){
			continue;
		}
		for(edge e : g[u]){
			int v = e.v,w = e.w;
			if(vis[v] == false and dis[v] > dis[u] + w){
				dis[v] = dis[u] + w;
				q.push({v,dis[v]});
			}
		}
	}
}
void astar(){
	dijkstra(s);
	pq.push({s,0,dis[t],to_string(s)});
	while(pq.empty() == false){
		astar_node now = pq.top();
		pq.pop();
		int u = now.u,step = now.step;
		string path = now.path;
		if(u == t){
			k --;
			if(k == 0){
				cout << path;
				return;
			}
			continue;
		}
		vis.reset();
		int tmp = 0;
		for(char c : path){
			if(c == '-'){
				vis[tmp] = true;
				tmp = 0;
			}else{
				tmp = tmp * 10 + c - '0';
			}
		}
		vis[tmp] = true;
		for(edge e : g[u]){
			int v = e.v,w = e.w;
			if(vis[v] == true){
				continue;
			}
			dijkstra(v);
			if(dis[t] > 1e6){
				continue;
			}
			pq.push({v,step + w,step + w + dis[t],path + '-' + to_string(v)});
		}
	}
	cout << "No";
}
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n >> m >> k >> s >> t;
	while(m --){
		int u,v,w;
		cin >> u >> v >> w;
		g[u].push_back({v,w});
	}
	astar();
	return 0;
}