记录编号	297954	评测结果	AAAAAAAAAA
题目名称	P服务点设置	最终得分	100
用户昵称	dateri	是否通过	通过
代码语言	C++	运行时间	0.018 s
提交时间	2016-08-19 16:24:54	内存使用	1.33 MiB

#include<cstdio>
#include<cstring>
#define getmin(a,b) ((a)<(b)?(a):(b))
#define getmax(a,b) ((a)>(b)?(a):(b))
using namespace std;
int a[105][105],n,p,max,min,ansnum=0x7fffffff;
int ans[105];
inline void dfs(int deep,int now)
{
	static int v[105];
	int i,j;
	max=-1;
	if(now>n)
	  return ;
	if(deep==p)
	{
	  for(i=0;i<n;i++)
	  {
		min=0x7fffffff;	
	    for(j=0;j<p;j++)
	      min=getmin(min,a[i][v[j]]);
	    max=getmax(min,max);
	  }
	  if(max<ansnum)
	  {
		ansnum=max;
		for(i=0;i<p;i++)
		  ans[i]=v[i];
	  }
	  return ;
	}
	for(i=now+1;i<n&&n-i+1>=p-deep;i++)
	{
	  v[deep]=i;
	  dfs(deep+1,i);
	}
	return ;
	  
}
int cc()
{
	freopen("djsc.in","r",stdin);
	freopen("djsc.out","w",stdout);
	int i,j,k,m,x,y,z;
	scanf("%d%d%d",&n,&m,&p);
	for(i=0;i<n;i++)
	  for(j=0;j<n;j++)
	    if(i!=j)
	      a[i][j]=0x7fffffff/2;
	while(m--)
	  scanf("%d%d%d",&x,&y,&z),a[x][y]=a[y][x]=z;
	for(k=0;k<n;k++)
	  if(i!=k)
	    for(i=0;i<n;i++)
	      for(j=0;j<n;j++)
	        if(i!=j&&j!=k&&a[i][j]>a[i][k]+a[k][j])
	          a[i][j]=a[i][k]+a[k][j];
	dfs(0,-1);
	for(i=0;i<p;i++)
	  printf("%d ",ans[i]);
	return 0;
}
int ccc=cc();
int main(){;}