记录编号	134639	评测结果	AAAAAAAAAA
题目名称	P服务点设置	最终得分	100
用户昵称	奶猹	是否通过	通过
代码语言	C++	运行时间	0.222 s
提交时间	2014-10-30 16:56:47	内存使用	0.30 MiB

#include<cstdio>
#include<cstring>
#include<climits>
#include<algorithm>
#define min(a,b) ((a)<(b)?(a):(b))

int n,m,p;
int a[101][101];
int rec[101],ans[101];
bool b[101]={0};
int maxn=INT_MIN,minn=INT_MAX,mnn=INT_MAX;

void init();
void work();
void outit();
void dfs(int );

int main()
{
    freopen("djsc.in","r",stdin);
   	freopen("djsc.out","w",stdout);
 	init();
    work();
    outit();
	//while(1);
    return 0;
}
void init()
{
	scanf("%d%d%d",&n,&m,&p);
	memset(a,0x3f,sizeof(a));
	for(int i=0;i<m;i++)
	{
		int x,y,z;
		scanf("%d%d%d",&x,&y,&z);
		a[x][y]=z;
		a[y][x]=z;
	}
	for(int i=0;i<n;i++)a[i][i]=0;
}
void work()
{
	for(int k=0;k<n;k++)
	for(int i=0;i<n;i++)
	for(int j=0;j<n;j++)
	a[i][j]=min(a[i][j],a[i][k]+a[k][j]);
	dfs(1);
}
void outit()
{
    std::sort(ans+1,ans+p+1);
	for(int i=1;i<=p;i++)
	printf("%d ",ans[i]);
}
void dfs(int x)//x当前点、num已选点数
{
	if(x==p+1)//说明上一个num为p
	{
		maxn=INT_MIN;
		for(int i=0;i<n;i++)//找题意中p个点到其他所有点的最远距离
		{
			bool flag=false;
			minn=INT_MAX;
			for(int j=1;j<=p;j++)//该方案中每个点到i的距离，找最短的
			{
				if(!a[i][rec[j]])//也就是rec[j]=i，直接跳过
				{flag=1;break;}
				if(a[i][rec[j]]<minn)
				minn=a[i][rec[j]];
			}
			if(!flag&&minn>maxn)maxn=minn;//最短中的最长的
		}
		if(maxn<mnn)//比上一个方案更优，更新
		{
			mnn=maxn;
			for(int j=1;j<=p;j++)
			ans[j]=rec[j];
		}
		return ;
	}
	for(int i=0;i<n;i++)
	{
		if(!b[i])
		{
			b[i]=1;
			rec[x]=i;
			dfs(x+1);
			b[i]=0;

		}
	}
}