P4467k短路求调

第1个样例过不去，提交上去20分

#include<bits/stdc++.h>
using namespace std;
const int maxn=50+5,maxm=maxn*(maxn+1);
int n,m,k,s,t;
struct edge{
	int to,nxt;
	long long val;
}e[maxm],e2[maxn];
int head[maxn],head2[maxn],cnt=0;
void add(int from,int to,long long val){
	e[++cnt].to=to,e[cnt].val=val;
	e[cnt].nxt=head[from],head[from]=cnt;
	e2[cnt].to=from,e2[cnt].val=val;
	e2[cnt].nxt=head2[to],head2[to]=cnt;
}long long dis[maxn];
string how[maxn];
bool vis[maxn];
struct node{
	int id;
	long long dist;
	string how_to;
	bool operator<(const node &x)const{
		if(dist==x.dist){
			return how_to>x.how_to;
		}return dist>x.dist;
	}
};
void check(){
	for(int i=1;i<=n;i++){
		cout<<dis[i]<<" ";
		printf("%d",(int)how[i][0]);
		for(int j=1;j<how[i].length();j++){
			printf("-%d",(int)how[i][j]);
		}cout<<endl;
	}
}void dijkstra(){
	for(int i=1;i<=n;i++){
		dis[i]=1e18,how[i]='z';
	}priority_queue<node>q;
	dis[t]=0,how[t]=(char)t;
	node tmp;
	tmp.id=t,tmp.how_to=how[t];
	q.push(tmp);
	while(!q.empty()){
		int now=q.top().id;
		q.pop();
		vis[now]=true;
		for(int i=head2[now];i;i=e2[i].nxt){
			if(dis[e2[i].to]>dis[now]+e2[i].val||dis[e2[i].to]==dis[now]+e2[i].val&&how[e2[i].to]>((char)e2[i].to)+how[now]){
				dis[e2[i].to]=dis[now]+e2[i].val;
				how[e2[i].to]=((char)e2[i].to)+how[now];
				if(!vis[e2[i].to]){
					q.push({e2[i].to,dis[e2[i].to],how[e2[i].to]});
				}	
			}
		}
	}for(int i=1;i<=n;i++){
		string str="";
		for(int j=1;j<how[i].length();j++){
			str+=how[i][j];
		}how[i]=str;
	}
}
struct point{
	int id;
	long long g,h;
	string how_g,how_h;
	bool operator<(const point &x)const{
		if(g+h==x.g+x.h){
			return how_g+how_h>x.how_g+x.how_h;
		}return g+h>x.g+x.h;
	}
};
void astar(){
	int count[maxn];
	memset(count,0,sizeof count);
	priority_queue<point>q;
	point now;
	now.id=s,now.g=now.h=0,now.how_g=(char)s,now.how_h=how[s];
	q.push(now);
	while(!q.empty()){
		now=q.top();
		q.pop();
		if(++count[now.id]==k&&now.id==t){
			string str=now.how_g+now.how_h;
			printf("%d",(int)str[0]);
			for(int i=1;i<str.length();i++){
				printf("-%d",(int)str[i]);
			}return;
		}for(int i=head[now.id];i;i=e[i].nxt){
			string str=now.how_g+((char)e[i].to)+how[e[i].to];
			bool flag[maxn],can=true;
			memset(flag,0,sizeof flag);
			for(int i=0;i<str.length();i++){
				if(flag[(int)str[i]]){
					can=false;
					break;
				}flag[(int)str[i]]=true;
			}if(can){
//				printf("%d",(int)str[0]);
//				for(int i=1;i<str.length();i++){
//					printf("-%d",(int)str[i]);
//				}cout<<"\n\n";
				q.push({e[i].to,now.g+e[i].val,dis[e[i].to],now.how_g+((char)e[i].to),how[e[i].to]});
			}
		}
	}printf("No");
	return;
}int main(){
	scanf("%d%d%d%d%d",&n,&m,&k,&s,&t);
	if(s==t){
		++k;
	}int from,to;
	long long val;
	for(int i=1;i<=m;i++){
		scanf("%d%d%lld",&from,&to,&val);
		add(from,to,val);
	}dijkstra();
	//check();
	astar();
	return 0;
}