A*模板，样例没过。。。

#include<bits/stdc++.h>
using namespace std;
int n,m,k,a,b,sum;
vector<pair<int,int> > w[51],g[51];
bool vis[51];
int dis[51];
queue<int> q;
struct node{
	int t,S,F;
	string go;
	void init(int a,int b,string c){
		t=a;
		S=b;
		F=b+dis[a];
		go=c;
	}
	friend bool operator<(node x,node y){
		if(x.F!=y.F) return x.F>y.F;
		else return x.t>y.t;
	}
};
priority_queue<node> sq;
void print(string str){
	printf("%d",a);
	for(int i=0;i<str.length();i++) printf("-%d",str[i]);
}
int main(){
	scanf("%d%d%d%d%d",&n,&m,&k,&a,&b);
	while(m--){
		int u,v,l;
		scanf("%d%d%d",&u,&v,&l);
		w[u].push_back(make_pair(v,l));
		g[v].push_back(make_pair(u,l));
	}
	memset(dis,127,sizeof(dis));
	q.push(b);
	vis[b]=1;
	dis[b]=0;
	while(!q.empty()){
		int now=q.front();
		vis[now]=0;
		for(int i=0;i<g[now].size();i++){
			int t=g[now][i].first,s=dis[now]+g[now][i].second;
			if(dis[t]>s){
				dis[t]=s;
				if(!vis[t]){
					vis[t]=1;
					q.push(t);
				}
			}
		}
		q.pop();
	}
	for(int i=1;i<=n;i++) sort(w[i].begin(),w[i].end());
	node start;
	start.init(a,0,"");
	sq.push(start);
	while(!sq.empty()){
		node now=sq.top();
		sq.pop();
		int t=now.t,s=now.S;
		string go=now.go;
		if(t==b){
			sum++;
			if(sum==k){
				print(go);
				return 0;
			}
		}else{
			for(int i=0;i<w[t].size();i++){
				int p=w[t][i].first,r=s+w[t][i].second;
				if(p!=a&&(int)go.find(p)!=-1) continue;
				node o;
				o.init(p,r,go+char(p));
				sq.push(o);
			}
		}
	}
	printf("No");
	return 0;
}