记录编号	389991	评测结果	AAAAAAAAAA
题目名称	P服务点设置	最终得分	100
用户昵称	人民不需要自由	是否通过	通过
代码语言	C++	运行时间	0.043 s
提交时间	2017-04-01 13:24:10	内存使用	0.33 MiB

#include<cstdio>
#define lon 999999999
#define MAX 100
using namespace std;
bool b[MAX+1];
int n,m,p,ans[MAX+1],s[MAX+1],len[MAX+1][MAX+1];
int mm=MAX;
void find(int);
int main()
{
	freopen("djsc.in","r",stdin);
	freopen("djsc.out","w",stdout);
	scanf("%d%d%d",&n,&m,&p);
	int a,b,c;
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			len[i][j]=lon;
	for(int i=1;i<=m;i++)
	{
		scanf("%d%d%d",&a,&b,&c);
		len[a][b]=c;
		len[b][a]=c;
	}
	for(int i=0;i<n;i++)
		for(int j=0;j<n;j++)
			for(int k=0;k<n;k++)
				if(len[i][k]+len[k][j]<len[i][j])
					len[i][j]=len[i][k]+len[k][j];
	for(int k=0;k<n;k++)
		len[k][k]=0;
	find(1);
	for(int i=1;i<=p;i++)
		printf("%d ",ans[i]);
	return 0;
}
void find(int k)
{
	for(int i=0;i<n;i++)
		if(b[i]==0)
		{
			s[k]=i;
			b[i]=1;
			if(s[k]<s[k-1])
			{
				b[i]=0;
				continue;
			}
			if(k==p)
			{
				int max=0;
				for(int z=0;z<n;z++)
				{
					int min=lon;
					for(int j=1;j<=p;j++)
					{
						if(len[s[j]][z]<min)
						{
							min=len[s[j]][z];
						}
					}
					if(min>max)
					{
						max=min;
					}
				}
				if(max<mm)
				{
					mm=max;
					for(int q=1;q<=p;q++)
						ans[q]=s[q];
				}
			}
			else
				find(k+1);
			b[i]=0;
		}
}