题号:P4467

大体思路就是A* + string保存路径。 代码如下:

#include<bits/stdc++.h>
using namespace std;
int n,m,k,st,ed;
struct pos
{
	int v,w;
};vector<pos>g[1010];vector<pos>fan[1010];
int dis[1010];bool vis[1010];
int guj[1010];
vector<string>chu[1010];
struct node
{
	int id;int dist;int gu;string lu;
	friend bool operator < (node a,node b)
	{
		return a.gu+a.dist>b.gu+b.dist;
	}
};
void spfa()
{
	memset(dis,0x3f,sizeof(dis));
	queue<int>q;
	q.push(ed);vis[ed] = 1;dis[ed] = 0;
	while(!q.empty())
	{
		int u = q.front();
		q.pop();vis[u]=0;
		int l = fan[u].size();
		for(int i = 0;i<l;i++)
		{
			int v = fan[u][i].v;
			if(dis[v]>dis[u]+fan[u][i].w)
			{
				dis[v] = dis[u]+fan[u][i].w;
				if(!vis[v])
				{
					vis[v] = 1;
					q.push(v);
				}
			}
		}
	}
	for(int i = 1;i<=n;i++)
	{
		guj[i] = dis[i];
	}
	return;
}
int cnt = 0;
void Astar()
{
	int pre = 0;
	priority_queue<node>p;
	string star = "";star+=(st+'0');
	p.push(node{st,0,guj[st],star});
	while(!p.empty())
	{
		node u = p.top();
		p.pop();
//		cout<<u.lu<<endl;
		if(u.id==ed)
		{
			if(u.dist!=pre)
			{
				cnt++;
				chu[cnt].push_back(u.lu);
				pre = u.dist;
			}
			else
			{
				chu[cnt].push_back(u.lu);
			}
			if(cnt==k+1)return;
			continue;
		}
		int l = g[u.id].size();
		for(int i = 0;i<l;i++)
		{
			int v = g[u.id][i].v;
			if(u.lu.find(char(v+'0'))==string::npos)
			{
				string tmp = u.lu;
				tmp+='-';tmp+=(v+'0');
				p.push(node{v,u.dist+g[u.id][i].w,guj[v],tmp});			
			}
		}
	}
}
int main()
{
	cin>>n>>m>>k>>st>>ed;
	for(int i = 1;i<=m;i++)
	{
		int u,v,w;
		scanf("%d%d%d",&u,&v,&w);
		g[u].push_back(pos{v,w});fan[v].push_back(pos{u,w});
	}
	spfa();
	Astar();
	int num = 0,bel=-1;
	for(int i = 1;i<=cnt;i++)
	{
		num+=chu[i].size();
		if(num>k)
		{
			num-=chu[i].size();
			bel = i;
			break;
		}
	}
	if(bel==-1)
	{
		cout<<"No";
		return 0;
	}
	sort(chu[bel].begin(),chu[bel].end());
	cout<<chu[bel][k-num-1];
	return 0;
}