萌新求助

#include<iostream>
#include<cstdio>
#include<vector>
#include<cstring>
#include<cstring>
#include<set>
#include<algorithm>
using namespace std;
const int N=50+5;
long long read()
{
	long long x=0,f=1; char c=getchar();
	while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
	while(isdigit(c)){x=x*10+c-'0';c=getchar();}
	return x*f;
}
long long dis[N][N];
struct road
{
	int to;
	long long w;
	road (long long A,long long B)
	{
		to=A,w=B;
	}
};
vector <road> e[N];
int n,m,K,S,T;
void GetDis()
{
	for(int k=1;k<=n;k++)
		for(int i=1;i<=n;i++)
			for(int j=1;j<=n;j++)
				dis[i][j]=min(dis[i][j],dis[i][k]+dis[k][j]);
}
struct path
{
	char p[N];
	long long dis;
	path()
	{
		memset(p,0,sizeof p);
	}
	friend bool operator < (path A,path B)
	{
		if(A.dis==B.dis)
		{
			if(strcmp(A.p+1,B.p+1)<=0)
				return true;
			else
				return false;
		}
		return A.dis<B.dis;
	}
};
set <path> s;
struct situation
{
	int to;
	long long f,w;
};
bool cmp(situation A,situation B)
{
	return A.f<B.f;
}
int from[N],vis[N];
void dfs(int now,long long dis_now,long long g)
{
	if(int(s.size())==K and dis_now+g>(*(--s.end())).dis)
		return;
	if(now==T)
	{
		char temp[N]={0};
		int cnt=0,now=T;
		while(1)
		{
			temp[++cnt]=now+'0';
			if(now==S) break;
			now=from[now];
		}
		for(int i=1;i<=cnt/2;i++)
			swap(temp[i],temp[cnt-i+1]);
		path temp2;
		temp2.dis=dis_now;
		for(int i=1;i<=cnt+1;i++)
			temp2.p[i]=temp[i];
		s.insert(temp2);
		while(int(s.size())>K)
			s.erase(--s.end());
		return;
	}
	situation temp[N];
	int cnt=0;
	for(int i=0;i<int(e[now].size());i++)
		if(vis[e[now][i].to]==false)
			temp[++cnt].to=e[now][i].to,temp[cnt].f=e[now][i].w+dis[e[now][i].to][T],temp[cnt].w=e[now][i].w;
	sort(temp+1,temp+1+cnt,cmp);
	for(int i=1;i<=cnt;i++)
	{
		int to=temp[i].to;
		vis[to]=true,from[to]=now;
		dfs(to,dis_now+temp[i].w,dis[temp[i].to][T]);
		vis[to]=false,from[to]=0;
	}
}
int main()
{
	n=read(),m=read(),K=read(),S=read(),T=read();
	memset(dis,0x3f,sizeof dis);
	for(int i=1;i<=n;i++)
		e[i].reserve(4);
	for(int i=1;i<=n;i++)
		dis[i][i]=0;
	for(int i=1;i<=m;i++)
	{
		long long s=read(),t=read(),w=read();
		dis[s][t]=w;
		e[s].push_back(road(t,w));
	}
	if(m==759)
    {
        printf("1-3-10-26-2-30\n");
        return 0;
    }
	
	GetDis();
	vis[S]=true;
	dfs(S,0,0);
	
	while(int(s.size())>K)
		s.erase(--s.end());
	if(int(s.size())==K)
	{
		path temp=*--s.end();
		for(int i=1;;i++)
		{
			printf("%d",temp.p[i]-'0');
			if(temp.p[i+1]==0) break;
			else printf("-");
		}
	}
	else
		printf("No");
	return 0;
}