记录编号	271042	评测结果	TAAWWTEEEE
题目名称	[SCOI 2007]kshort	最终得分	20
用户昵称	YGOI_真神名曰驴蛋蛋	是否通过	未通过
代码语言	C++	运行时间	4.434 s
提交时间	2016-06-15 16:11:19	内存使用	3.74 MiB

#include <cstdio>
#include <cstring>
#include <vector>
#include <queue>
const int MAXNODE=51;
const int MAXPATH=51*51;
const int INF=0x6363636; 
int N,M,From,To,Kth;
int max_len,max_dis,Times,INDEX;
int ways[MAXPATH][MAXNODE];
int ways_dis[MAXNODE];
int sizeof_ways[MAXNODE];
int this_way[MAXNODE];
int sizeof_this_way;
bool vis[MAXNODE];
int SPFA=0;
//#define sizeof_ways(i) ways[i][0]
//#define this_way ways[0]
//#define sizeof_this_way ways[0][0]
typedef struct Path{
	int to,dis,next;
	Path(const int&t=-1,const int&d=0x7ffffff,const int&n=-1){to=t;dis=d;next=n;}
	bool operator < (const Path&a)const{return dis>a.dis;}
}Node;
std::vector <Path> arr;
struct Pic{
	int dis[MAXNODE];
	int head[MAXNODE];
	int table[MAXNODE][MAXNODE];
	Pic(){clear();}
	void clear(){
		memset(head,-1,sizeof(head));
		memset(table,-1,sizeof(table));
	}
	void View(){
		for(int i=1;i<=N;++i){
			for(int j=N;j>=1;--j){
				printf("Line %d::to->%d dis->%d\n",i,j,table[i][j]);
			}
		}
	}
	void add(const int&from,const int&to,const int&dis){
		table[from][to]=dis;
	}
	void ViewDis(){
		printf("\nWatching\n");
		for(int i=0;i<=N;++i){
			printf("dis[%d]=%d\n",dis,dis[i]);
		}
	}
	#define pos to
	bool dijsa(){
		memset(dis,63,sizeof(dis));
		std::priority_queue<Node>q;
		q.push( Node(To,0) );dis[To]=0;
		while(!q.empty()){
			Node p=q.top();q.pop();
			if(dis[p.pos]!=p.dis)continue;
			for(int i=1;i<=N;++i){
				if(table[p.pos][i]==-1)continue;
				if(dis[i] > table[p.pos][i]+p.dis){
					dis[i] = table[p.pos][i]+p.dis;
					q.push(Node(i,dis[i]));
				}
			}
		}return dis[From]==dis[0];
	}
	#undef pos
	bool DFSBNS(const int&now,const int&distence){
		//printf("    Height : %d now->%d dis->%d\n",++SPFA,now,distence);
		if(now==To){
			//printf(">>Get:%d\n",SPFA);
			if(distence<=max_len){
				ways_dis[++Times]=distence;
				sizeof_ways[Times]=sizeof_this_way;
				for(int i=1;i<=sizeof_this_way;++i)
					ways[Times][i]=this_way[i];
				//printf("[[Less than:%d\n",SPFA);
				--SPFA;
				return Times==Kth;
			}else if(distence<max_dis){
					max_dis=distence;
					//printf("[[No Less than:%d\n",SPFA);
				}
			--SPFA;
			return false;
		}
		int temp=distence+dis[now];
		if(temp>max_len){
			if(temp<max_dis)
				max_dis=temp;
			//printf("||Temp?:%d\n",SPFA);
			--SPFA;
			return false;
		}
		//printf("+++dis[%d]->%d  dis[0]->%d\n",now,dis[now],dis[0]);
		if(dis[now]==dis[0]){/*printf("\n~~Can't get:%d\n",SPFA);*/return false;}
		for(int i=1;i<=N;++i){
			if(table[now][i]==-1)continue;
			if(vis[i]==false){
				vis[i]=true;
				this_way[++sizeof_this_way]=i;
				if(DFSBNS(i,distence+table[now][i]))
					{--SPFA;return true;}
				else {--sizeof_this_way;vis[i]=false;}
			}
		}--SPFA;
		//printf("-----Turn Ending:%d\n",SPFA);
		return false;
	}
	void print(){
		for(int i=1;i<sizeof_ways[INDEX];++i){
			printf("%d-",ways[INDEX][i]);
		}printf("%d\n",ways[INDEX][sizeof_ways[INDEX]]);
	}
	bool work(){
		max_len=dis[From];INDEX=0;
		int last=0,POTER=0;
		while(++POTER){
			//printf("Number:%d\n",POTER);
			max_dis=INF;Times=0;
			memset(vis,0,sizeof(vis));
			vis[From]=1;
			sizeof_this_way=1;
			this_way[1]=From;
			if(DFSBNS(From,0)){
				last=Kth-last;
				for(int i=1;i<=Kth;++i){
					if(ways_dis[i]==max_len){
						--last;
						if(!last)INDEX=i;
					}
				}return true;
			}
			else if(max_dis==INF)return false;
			else {last=Times;max_len=max_dis;}
			//Stop();
		}
	}
	void init(){
		scanf("%d%d%d%d%d",&N,&M,&Kth,&From,&To);
		for(int i=1,a,b,c;i<=M;++i){
			scanf("%d%d%d",&a,&b,&c);
			arr.push_back(Path(b,c,a));
		}
	}
	void AddP(){
		clear();
		const int sizen=arr.size();
		for(int i=0;i<sizen;++i)
			add(arr[i].to,arr[i].next,arr[i].dis);
	}
	void Add(){
		clear();
		const int sizen=arr.size();
		for(int i=0;i<sizen;++i)
			add(arr[i].next,arr[i].to,arr[i].dis);
		arr.clear();
	}
	void Stop(){while(getchar()!='e');}
	int doing(){
		freopen("bzoj_1073.in","r",stdin);freopen("bzoj_1073.out","w",stdout);
		init();AddP();
		dijsa();
		/*ViewDis();Stop();*/
		Add();//View();
		if(work())print();
		else puts("No");
		//Stop();
		return 0;
	}
}a;
int main(){ a.doing(); }