记录编号	381494	评测结果	AAAAAAAAAA
题目名称	P服务点设置	最终得分	100
用户昵称	泪寒之雪	是否通过	通过
代码语言	C++	运行时间	0.331 s
提交时间	2017-03-11 20:23:39	内存使用	0.35 MiB

#include<bits/stdc++.h>
#define inf 2E+7
using namespace std;
int i,j,k,top,ans,n,m,f[101][101],a,b,c,maxx=2E+7,p,gg[101],g[101],kk[101],bb[101];
void dfs(int top)
{
   if (top==p+1)
    {
    	memset(gg,127,sizeof gg);
       for (int i=1;i<=p;i++)
    	for (int j=0;j<n;j++)
    	  gg[j]=min(gg[j],f[g[i]][j]);
    	int nodee=gg[0];
       for (int i=1;i<n;i++)
         nodee=max(nodee,gg[i]);
       if (nodee<maxx)
        {
       	  maxx=nodee;
       	  for (int i=0;i<n;i++)
       	   kk[i]=bb[i];
	    }
    	
    return;	
    }
   for (int i=0;i<n;i++)
    if (!bb[i])
	{
       bb[i]=1;
       g[top]=i;
	   dfs(top+1);
	   bb[i]=0;	
	}
}
int main ()
{
	freopen("djsc.in","r",stdin);
	freopen("djsc.out","w",stdout);
	//memset(g,127,sizof g);
	scanf("%d%d%d",&n,&m,&p);
	for (i=0;i<n;i++)
	 for (j=0;j<n;j++)
	  f[i][j]=inf;

	for (i=1;i<=m;i++)
	{
	 scanf("%d%d%d",&a,&b,&c);
	 f[a][b]=c;
	 f[b][a]=c;	 
		}
	for (k=0;k<n;k++)
	 for (i=0;i<n;i++)
	  for (j=0;j<n;j++)
	   f[i][j]=min(f[i][j],f[i][k]+f[k][j]);
	for (i=0;i<n;i++)
	  f[i][i]=0;
	dfs(1);
	for (i=0;i<n;i++)
	 if (kk[i]) printf("%d ",i);
/*	for (i=0;i<n;i++)
	{
	 gg=-inf;
	  for (j=0;j<n;j++)
	   if (i!=j) gg=max(gg,f[i][j]);
	 if (gg<minn) {
	 	minn=gg;
	 	top=i;
	 } 
	}    
	printf("%d",top);*/
}