记录编号	50372	评测结果	AAAAAAAAAA
题目名称	P服务点设置	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	0.057 s
提交时间	2012-11-19 21:22:34	内存使用	3.23 MiB

#include<iostream>
#include<fstream>
using namespace std;
int n[100][100]={0},a,b,c,city,road,temp[100]={0},ansmax=99999,p;
int i,k,leng[100][100],j,lp=0,answer[100]={0};
const int MAX=9000000;
int min(int x,int y){
	return (x<y)?x:y;
}
int shortest(void){
	int nowmin=MAX,nowmax=0;
	for(i=0;i<city;i++){
		nowmin=MAX;
		for(j=0;j<lp;j++){
			if(leng[i][temp[j]]<nowmin) nowmin=leng[i][temp[j]];
		}
		if(nowmin>nowmax) nowmax=nowmin;
	}
	return nowmax;
}
/*void dfs(int x,int nowmax,int flag){//到x
	cout<<lp<<" "<<x<<"sb"<<endl;
	for(i=0;i<lp;i++) cout<<temp[i]<<" ";
	cout<<endl;
	if(flag) nowmax=shortest();
	if(lp==p||x==city){
		if(lp==p&&nowmax<ansmax){
			for(i=0;i<p;i++) answer[i]=temp[i];
			ansmax=nowmax;
		}
		if(flag) lp--;
		return;
	}
	if(lp+city-x>=p-1) dfs(x+1,nowmax,0);
	lp++,temp[lp]=x;
	dfs(x+1,nowmax,1);
	if(flag) lp--;
}*/
void dfs(int x,int nowmax){//到x
	//cout<<lp<<endl;
	//nowmax=shortest();
	//cout<<x<<" "<<lp<<"sb"<<endl;
	/*for(int km=0;km<lp;km++) cout<<temp[km]<<" ";
	cout<<endl;*/
	if(lp==p){
		nowmax=shortest();
		if(nowmax<ansmax){
			for(i=0;i<p;i++) answer[i]=temp[i];
			ansmax=nowmax;
		}
		lp--;
		return;
	}
	int i;
	for(i=x+1;i<city;i++){
		//cout<<x<<" "<<city<<" "<<i<<" "<<lp<<endl;
		temp[lp]=i,lp++;
		dfs(i,nowmax);
	}
	lp--;
	//cout<<lp<<"sb"<<endl;
	return;
}
int main(){
    ifstream fin("djsc.in");
    ofstream fout("djsc.out");
    fin>>city>>road>>p;
    for(k=0;k<city;k++){
		for(i=0;i<city;i++){
			leng[k][i]=MAX;
		}
    }
    for(i=1;i<=road;i++){
        fin>>a>>b>>c;
        n[a][b]=c;
        n[b][a]=c;
        leng[a][b]=c;
        leng[b][a]=c;
    }
 
	for(k=0;k<city;k++){
		for(i=0;i<city;i++){
			for(j=0;j<city;j++){
				if(leng[i][k]+leng[k][j]<leng[i][j]){
					leng[i][j]=leng[i][k]+leng[k][j];
				}
			}
		}
	}
	for(k=0;k<city;k++) leng[k][k]=0;
	/*for(i=0;i<city;i++){
		temp[0]=i,lp=1;
		dfs(i,MAX);
	}*/
	dfs(-1,MAX);
	for(i=0;i<p;i++) fout<<answer[i]<<" ";
	cout<<endl;
	fin.close();
	fout.close();
	return 0;
}